<|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.

120. Archipelago

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


Archipelago Ber-Islands consists of N islands that are vertices of equiangular and equilateral N-gon. Islands are clockwise numerated. Coordinates of island N1 are (x1, y1), and island N2 – (x2, y2). Your task is to find coordinates of all N islands.


Input

In the first line of input there are N, N1 and N2 (3£ N£ 150, 1£ N1,N2£N, N1¹N2) separated by spaces. On the next two lines of input there are coordinates of island N1 and N2 (one pair per line) with accuracy 4 digits after decimal point. Each coordinate is more than -2000000 and less than 2000000.


Output

Write N lines with coordinates for every island. Write coordinates in order of island numeration. Write answer with 6 digits after decimal point.


Sample Input

4 1 3
1.0000 0.0000
1.0000 2.0000
Sample Output

1.000000 0.000000
0.000000 1.000000
1.000000 2.000000
2.000000 1.000000
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged Problem Statement
You have a regular N-gon (vertices numbered 1…N in clockwise order). You know the 2D coordinates of two distinct vertices, say index a and index b. Recover the coordinates of all N vertices in index order, printing each with six decimal places.

2. Key Observations
- A regular N-gon is inscribed in a circle (circumcircle) of some center C and radius R.
- The central angle between vertices a and b is Δ = 2π·|b−a|/N.
- The straight-line distance d = |A−B| is the chord length spanning that angle.
- From the chord–radius relation: d = 2R·sin(Δ/2), so R = d/(2·sin(Δ/2)).
- The center C lies on the perpendicular bisector of segment AB, at distance h = (d/2)/tan(Δ/2) from the midpoint M of AB.
- Once C and R are known, if φ is the polar angle of A relative to C, then the i-th vertex (counting clockwise) has angle φ_i = φ + 2π·(a−i)/N, and its coordinates are C + R·(cosφ_i, sinφ_i).

3. Full Solution Approach
1. Read N, a, b and the given points A=(x_a,y_a), B=(x_b,y_b).
2. If a>b, swap a↔b (and the stored points), so that a<b.
3. Compute d = distance(A,B).
4. Compute half-angle α = π·(b−a)/N (so that Δ=2α).
5. Compute radius R = d / (2·sin α).
6. Compute midpoint M = (A+B)/2.
7. Compute h = (d/2) / tan α.
8. The vector from A to B is v=(dx,dy)=(B.x−A.x, B.y−A.y).
   A perpendicular direction is p = (dy, −dx) (rotating v by +90°).
   Its length is d, so scaling p by h/d makes its length h.
9. Choose center C = M + p_scaled.  (This orientation matches the clockwise numbering.)
10. Compute φ, the polar angle of A about C. The reference code derives it from asin((A.y−C.y)/R) and fixes the quadrant with acos((A.x−C.x)/R); this equals atan2(A.y−C.y, A.x−C.x).
11. For i from 1 to N:
    - If i==a, output A; if i==b, output B.
    - Otherwise, compute φ_i = φ + 2π·(a−i)/N, and P_i = C + R·(cosφ_i, sinφ_i). Output P_i.

All steps take O(N) time and O(N) memory for the stored points.

4. C++ Implementation
```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;
};

using Point = complex<long double>;

int n, a, b;
vector<Point> points;

void read() {
    cin >> n >> a >> b;
    points.assign(n + 1, Point());
    long double x, y;
    cin >> x >> y;
    points[a] = Point(x, y);
    cin >> x >> y;
    points[b] = Point(x, y);
}

void solve() {
    // The islands are vertices of a regular N-gon listed clockwise, and we know
    // two of them (indices a, b). The chord between vertices a and b subtends a
    // central angle of 2*pi*(b-a)/n, so the circumradius is dist / 2 /
    // sin(pi*(b-a)/n) and the circle centre lies on the perpendicular bisector
    // of that chord (offset by the half-chord over tan of the half-angle).
    // Once the centre and the angular position phi of vertex a are known, every
    // other vertex i sits at angle phi + 2*pi*(a-i)/n on the circle.

    if(a > b) {
        swap(a, b);
    }

    const long double PI = 3.14159265358979323846L;
    long double dist = abs(points[b] - points[a]);
    long double radius = dist / sin(PI * (b - a) / n) / 2;

    Point mid = (points[a] + points[b]) / 2.0L;
    Point center =
        mid +
        Point(
            (points[b].imag() - points[a].imag()) / tan(PI * (b - a) / n) / 2,
            -(points[b].real() - points[a].real()) / tan(PI * (b - a) / n) / 2
        );

    long double phi = asin((points[a].imag() - center.imag()) / radius);
    if(acos((points[a].real() - center.real()) / radius) > PI / 2) {
        phi = (phi >= 0 ? PI - phi : -PI - phi);
    }

    for(int i = 1; i <= n; i++) {
        if(i != a && i != b) {
            long double delta = phi + 2 * PI * (a - i) / n;
            points[i] =
                center + Point(radius * cos(delta), radius * sin(delta));
        }
    }

    cout << fixed << setprecision(6);
    for(int i = 1; i <= n; i++) {
        cout << points[i].real() << " " << points[i].imag() << "\n";
    }
}

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;
}
```

5. Python Implementation with Detailed Comments
```python
import math
import sys

def main():
    data = sys.stdin.read().split()
    N, a, b = map(int, data[:3])
    xa, ya = map(float, data[3:5])
    xb, yb = map(float, data[5:7])
    A = complex(xa, ya)
    B = complex(xb, yb)

    # Ensure a < b by swapping if needed
    if a > b:
        a, b = b, a
        A, B = B, A

    # 1) Chord length
    d = abs(B - A)

    # 2) Half central angle α = π*(b-a)/N
    PI = math.pi
    alpha = PI * (b - a) / N

    # 3) Circumradius R = d / (2 sin α)
    R = d / (2 * math.sin(alpha))

    # 4) Midpoint M of AB
    M = (A + B) / 2

    # 5) Distance from M to center: h = (d/2)/tan α
    h = (d / 2) / math.tan(alpha)

    # 6) Perpendicular direction: rotate (dx,dy)->(dy,-dx), normalize to h
    dx = B.real - A.real
    dy = B.imag - A.imag
    perp = complex(dy, -dx) * (h / d)

    # 7) Choose center C = M + perp
    C = M + perp

    # 8) Base angle φ of A around C
    phi = math.atan2(A.imag - C.imag, A.real - C.real)

    # 9) Generate all N vertices
    step = 2 * PI / N
    out = []
    for i in range(1, N+1):
        if i == a:
            P = A
        elif i == b:
            P = B
        else:
            theta = phi + step * (a - i)  # clockwise numbering
            P = C + R * complex(math.cos(theta), math.sin(theta))
        out.append(f"{P.real:.6f} {P.imag:.6f}")

    sys.stdout.write("\n".join(out))

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