p136.ans1
======================
YES
-1.000 1.000
1.000 -1.000
3.000 1.000
1.000 3.000

=================
p136.ans2
======================
NO

=================
p136.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const double eps = 1e-6;

int n;
vector<double> mx, my;

void read() {
    cin >> n;
    mx.resize(n);
    my.resize(n);

    for(int i = 0; i < n; i++) {
        cin >> mx[i] >> my[i];
    }
}

vector<double> solve_system(vector<double> mids) {
    int n = mids.size();

    double x1;
    if(n % 2 == 1) {
        x1 = 0;
        for(int i = 0; i < n; i++) {
            if(i % 2 == 0) {
                x1 += mids[i];
            } else {
                x1 -= mids[i];
            }
        }
    } else {
        x1 = 0;
    }

    vector<double> x(n);
    x[0] = x1;
    for(int i = 0; i < n - 1; i++) {
        x[i + 1] = 2 * mids[i] - x[i];
    }

    if(abs(x[n - 1] + x[0] - 2 * mids[n - 1]) > eps) {
        return {};
    }

    return x;
}

void solve() {
    // The two main observations are:
    //   (1) The hint in the problem statement is that we don't care about
    //       edge intersections.
    //   (2) The midpoint of (x1, y1) and (x2, y2) is ((x1+x2)/2,
    //       (y1+y2)/2), and so the X and Y dimensions are independent.
    //
    // Therefore, we can solve the following system:
    //   x1 + x2 = 2 * mx1
    //   x2 + x3 = 2 * mx2
    //     ...
    //   xn + x1 = 2 * mxn
    //
    // (and the analogous one for y).
    //
    // To solve this system, we can notice that we can split into two cases by
    // parity:
    //   (1) N is odd. Then we have either 0 or 1 solutions. If there is a
    //       single solution, we can get x1 and then recover everything. To
    //       get x1, we will get:
    //          2 * x1 = 2 * (mx1 - mx2 + mx3 - mx4 + ... + mxn).
    //          x1 = (mx1 - mx2 + mx3 - mx4 + ... + mxn)
    //   (2) N is even. Then we have either 0 or infinitely many solutions. If
    //   that's the case, we will try x1 = 0.
    //
    // After we have decided on x1, recovering is simple by x{i+1} = 2 * mxi -
    // xi. Now we have the x1...xn candidate. We want to re-validate that this
    // is a solution to this system.

    vector<double> x = solve_system(mx);
    vector<double> y = solve_system(my);

    if(x.empty() || y.empty()) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    for(int i = 0; i < n; i++) {
        cout << setprecision(3) << fixed << x[i] << " " << y[i] << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p136.in1
======================
4
0 0
2 0
2 2
0 2

=================
p136.in2
======================
4
0 0
2 0
2 2
1 3

=================
statement.txt
======================
136. Erasing Edges

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Little Johnny painted on a sheet of paper a polygon with N vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.


Input

The first line of the input contains the integer number N (3<=N<=10 000). Then, N lines will follow, each of them containing 2 real numbers, separated by blanks: xi and yi. (xi,yi) are the coordinates of the middle point of the edge #i. The coordinates will be given with at most 3 decimal places.


Output

Print a line containing the word "YES", if the polygon can be redrawn, or "NO", if there exists no polygon having the given coordinates for the middle points of its edges. If the answer is "YES", then you should print N more lines, each of them containing two real numbers, separated by a blank, representing the X and Y coordinates of the vetices of the polygon. The coordinates should be printed with at least 3 decimal places. You should output the cordinates for vertex #1 first, for vertex #2 second and so on.. In order to decide which vertex of the polygon is #1,#2,..,#N, you should know that for every 1<=i<=N-1, edge #i connects the vertices labeled i and i+1. Edge #N connects the vertices N and 1.


Hint

The polygon may contain self-intersections. Although in many geometric problems, self-intersections only make things more difficult, in this case, they make things a lot easier.


Sample Input #1

4
0 0
2 0
2 2
0 2
Sample Output #1

YES
-1.000 1.000
1.000 -1.000
3.000 1.000
1.000 3.000
Sample Input #2

4
0 0
2 0
2 2
1 3
Sample Output #2

NO
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

=================
