<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
1) Abridged problem statement
- You are given N points Mi = (mxi, myi), i = 1..N, which are the midpoints of the edges of a polygon (possibly self-intersecting). Edge i connects vertex Vi to Vi+1, and edge N connects VN to V1.
- Determine whether there exists a polygon V1..VN whose edge midpoints are exactly Mi. If yes, print YES and one valid sequence of vertices; otherwise print NO.

2) Key observations
- Midpoint constraints give linear equations along each axis independently:
  Xi + Xi+1 = 2*mxi and Yi + Yi+1 = 2*myi for i = 1..N, with VN+1 = V1.
- These are identical 1D systems for X and Y; solve them separately.
- Define the recurrence: Xi+1 = 2*mxi − Xi for i = 1..N−1.
- The closing equation XN + X1 = 2*mxN enforces consistency:
  - N odd: Unique solution; X1 = m1 − m2 + m3 − ... + mN (alternating sum). Then reconstruct all Xi by the recurrence.
  - N even: Consistency condition is m1 − m2 + m3 − ... − mN = 0. If it fails, no solution. If it holds, infinitely many solutions; pick any X1 (e.g., 0) and reconstruct.
- Apply the same logic to Y. The polygon exists iff both axes are solvable.
- Use a small epsilon for floating-point comparisons. Output coordinates with at least 3 decimals.

3) Full solution approach
- Read N and the N midpoint coordinates Mi.
- Solve 1D system for X:
  - If N is odd, compute X1 as the alternating sum of mx and reconstruct Xi+1 = 2*mxi − Xi.
  - If N is even, pick X1 = 0, reconstruct, and verify the last equation XN + X1 = 2*mxN within epsilon (this implicitly checks the alternating-sum condition).
- Do the same for Y.
- If either axis is inconsistent, print NO. Otherwise print YES and the N vertex coordinates (Xi, Yi).
- Complexity: O(N) time and O(N) memory.

4) C++ implementation with detailed comments
```cpp
#include <bits/stdc++.h>
using namespace std;

static const double EPS = 1e-6;

// Solve one axis: given mids[i] = midpoint coordinate for edge i (0-based),
// find x[0..n-1] s.t. x[i] + x[(i+1)%n] = 2*mids[i].
// Return empty vector if no solution.
vector<double> solve_axis(const vector<double>& mids) {
    int n = (int)mids.size();
    vector<double> x(n);

    // Choose/derive x1 depending on parity
    if (n % 2 == 1) {
        // Unique solution for odd n:
        // x1 = m1 - m2 + m3 - ... + mN (1-based), i.e., alternating sum starting with +.
        double x1 = 0.0;
        for (int i = 0; i < n; ++i) {
            x1 += (i % 2 == 0 ? +mids[i] : -mids[i]);
        }
        x[0] = x1;
    } else {
        // Even n: either none or infinitely many solutions. Pick an arbitrary x1 (e.g., 0).
        x[0] = 0.0;
    }

    // Reconstruct by recurrence: x[i+1] = 2*mids[i] - x[i]
    for (int i = 0; i < n - 1; ++i) {
        x[i + 1] = 2.0 * mids[i] - x[i];
    }

    // Validate the closing equation: x[n-1] + x[0] == 2*mids[n-1]
    if (fabs((x[n - 1] + x[0]) - 2.0 * mids[n - 1]) > EPS) {
        return {}; // inconsistent system
    }
    return x;
}

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

    int n;
    if (!(cin >> n)) return 0;

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

    vector<double> X = solve_axis(mx);
    vector<double> Y = solve_axis(my);

    if (X.empty() || Y.empty()) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    cout.setf(ios::fixed);
    cout << setprecision(3);
    for (int i = 0; i < n; ++i) {
        cout << X[i] << ' ' << Y[i] << '\n';
    }
    return 0;
}
```

5) Python implementation with detailed comments
```python
import sys

EPS = 1e-6

def solve_axis(mids):
    """
    Given mids[i] = midpoint coordinate for edge i (0-based),
    find x[0..n-1] such that x[i] + x[(i+1)%n] = 2*mids[i].
    Return [] if no solution exists.
    """
    n = len(mids)
    x = [0.0] * n

    if n % 2 == 1:
        # Unique solution: x1 = m1 - m2 + m3 - ... + mN
        x1 = 0.0
        for i, m in enumerate(mids):
            x1 += m if (i % 2 == 0) else -m
        x[0] = x1
    else:
        # Even n: pick any x1, e.g., 0, then validate the last equation
        x[0] = 0.0

    # Reconstruct via recurrence
    for i in range(n - 1):
        x[i + 1] = 2.0 * mids[i] - x[i]

    # Validate closing equation
    if abs((x[-1] + x[0]) - 2.0 * mids[-1]) > EPS:
        return []
    return x

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    mx = [0.0] * n
    my = [0.0] * n
    for i in range(n):
        mx[i] = float(next(it))
        my[i] = float(next(it))

    X = solve_axis(mx)
    Y = solve_axis(my)

    if not X or not Y:
        print("NO")
        return

    print("YES")
    for i in range(n):
        print(f"{X[i]:.3f} {Y[i]:.3f}")

if __name__ == "__main__":
    main()
```