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

228. Archipelago
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Ber-islands Archipelago consists of N islands and has a form of regular N-gon. Islands are numbered in a clockwise order. Coordinates of the N1-th island are (X1, Y1), and of the N2-th island are - (X2, Y2). You are to write a program which will find coordinates of all islands.

Input
The input contains three integers N, N1, N2 (3<=N<=150, 1<=N1,N2<=N, N1<>N2). The following two pairs of real numbers are coordinates of N1-th and N2-th islands. All absolute values of coordinates do not exceed 10^6. All numbers separated by white spaces.

Output
Output coordinates of the islands in order of numeration on separate lines. The computed coordinates should be exact to six digits after the decimal point.

Sample test(s)

Input
4 1 3
1.0000 0.0000
1.0000 2.0000

Output
1.000000 0.000000
0.000000 1.000000
1.000000 2.000000
2.000000 1.000000
Author:	Michael R. Mirzayanov
Resource:	---
Date:	--

<|response|>
## 1) Abridged problem statement (concise)

You are given a **regular \(N\)-gon** (vertices numbered **clockwise** from \(1\) to \(N\)).  
Coordinates of vertex \(N_1\) are \((X_1,Y_1)\) and of vertex \(N_2\) are \((X_2,Y_2)\).  
Reconstruct and output coordinates of **all \(N\)** vertices in order \(1..N\), each on a separate line, with **6 digits after the decimal point**.

Constraints: \(3 \le N \le 150\), \(N_1 \ne N_2\).

---

## 2) Key observations

1. All vertices of a regular \(N\)-gon lie on a **common circumcircle** with center \(O\) and radius \(R\).
2. If we know \(O\), then every vertex is obtained by **rotating** one known radius vector by multiples of \(2\pi/N\).
3. Let \(A\) be vertex \(N_1\) and \(B\) be vertex \(N_2\). The number of clockwise steps from \(N_1\) to \(N_2\) is:
   \[
   k = (N_2 - N_1 + N)\bmod N
   \]
   So the central angle between them is:
   \[
   \theta = \frac{2\pi k}{N}
   \]
4. Chord formula for circle: if chord \(AB\) subtends central angle \(\theta\),
   \[
   |AB| = 2R\sin(\theta/2)
   \Rightarrow
   R = \frac{|AB|}{2\sin(\theta/2)}
   \]
5. The center \(O\) lies on the **perpendicular bisector** of chord \(AB\). If \(M=(A+B)/2\) is midpoint of \(AB\), then
   \[
   |OM| = R\cos(\theta/2)
   \]
   so \(O = M \pm \hat{p}\,R\cos(\theta/2)\), where \(\hat{p}\) is a unit vector perpendicular to \(AB\).
6. Once \(O\) is chosen consistently, vertex \(i\) is:
   \[
   P_i = O + \text{rotate}(A-O,\,-2\pi(i-N_1)/N)
   \]
   (negative sign because numbering is **clockwise**, while math rotation is positive CCW).

---

## 3) Full solution approach

1. Read \(N, N_1, N_2\) and points \(A, B\).
2. Compute \(k=(N_2-N_1+N)\bmod N\) and \(\theta = 2\pi k/N\).
3. Compute:
   - Midpoint \(M=(A+B)/2\)
   - Half-chord length \(d=|AB|/2\)
   - Radius \(R = d / \sin(\theta/2)\)
4. Compute a unit perpendicular direction to the chord, e.g.
   - \( \text{perp} = \text{unit}((A-B)^\perp) \) where \((x,y)^\perp=(-y,x)\)
5. Compute center:
   \[
   O = M + \text{perp}\cdot(R\cos(\theta/2))
   \]
   (This picks one of the two symmetric centers; this consistent choice matches the clockwise generation used next.)
6. For each \(i=1..N\):
   - angle \(a = -2\pi(i-N_1)/N\)
   - point \(P_i = O + \text{rotate}(A-O, a)\)
   - print \(P_i\)

Complexity: \(O(N)\) time, \(O(1)\) extra memory.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    Point(double x_=0, double y_=0) : x(x_), y(y_) {}

    Point operator + (const Point& o) const { return Point(x + o.x, y + o.y); }
    Point operator - (const Point& o) const { return Point(x - o.x, y - o.y); }
    Point operator * (double k)     const { return Point(x * k, y * k); }
    Point operator / (double k)     const { return Point(x / k, y / k); }

    // Euclidean length
    double norm() const { return hypot(x, y); }

    // Rotate vector around origin by angle a (radians), CCW positive
    Point rotate(double a) const {
        double c = cos(a), s = sin(a);
        return Point(x * c - y * s, x * s + y * c);
    }

    // Perpendicular (+90 degrees): (x, y) -> (-y, x)
    Point perp() const { return Point(-y, x); }

    // Unit vector (assumes non-zero length)
    Point unit() const {
        double len = norm();
        return (*this) / len;
    }
};

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

    int N, N1, N2;
    cin >> N >> N1 >> N2;

    Point A, B;
    cin >> A.x >> A.y;
    cin >> B.x >> B.y;

    const double PI = acos(-1.0);

    // k = number of clockwise steps from vertex N1 to vertex N2
    int k = (N2 - N1 + N) % N;

    // central angle AOB
    double theta = 2.0 * PI * k / N;

    // chord midpoint
    Point M = (A + B) / 2.0;

    // half chord length |AB|/2
    double halfLen = (B - A).norm() / 2.0;

    // circumradius via chord formula: halfLen = R * sin(theta/2)
    double R = halfLen / sin(theta / 2.0);

    // Direction along perpendicular bisector.
    // Using (A - B).perp() chooses a consistent side.
    Point perpDir = (A - B).perp().unit();

    // distance from midpoint to center along the perpendicular bisector
    double OM = R * cos(theta / 2.0);

    // choose one of the two possible centers
    Point O = M + perpDir * OM;

    cout << fixed << setprecision(6);

    // Generate all vertices in numeric order 1..N.
    // Clockwise numbering => negative rotation in usual math convention.
    for (int i = 1; i <= N; i++) {
        double ang = -2.0 * PI * (i - N1) / N;
        Point Pi = O + (A - O).rotate(ang);
        cout << Pi.x << " " << Pi.y << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import math

class Point:
    __slots__ = ("x", "y")
    def __init__(self, x=0.0, y=0.0):
        self.x = float(x)
        self.y = float(y)

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, k: float):
        return Point(self.x * k, self.y * k)

    def __truediv__(self, k: float):
        return Point(self.x / k, self.y / k)

    def norm(self) -> float:
        return math.hypot(self.x, self.y)

    def perp(self):
        # +90 degrees: (x, y) -> (-y, x)
        return Point(-self.y, self.x)

    def unit(self):
        length = self.norm()
        return self / length

    def rotate(self, a: float):
        # Rotate around origin by angle a (radians), CCW positive
        c = math.cos(a)
        s = math.sin(a)
        return Point(self.x * c - self.y * s, self.x * s + self.y * c)


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    N = int(next(it))
    N1 = int(next(it))
    N2 = int(next(it))

    A = Point(float(next(it)), float(next(it)))
    B = Point(float(next(it)), float(next(it)))

    # Steps clockwise from N1 to N2
    k = (N2 - N1 + N) % N

    # Central angle between A and B
    theta = 2.0 * math.pi * k / N

    # Midpoint of chord AB
    M = (A + B) / 2.0

    # Half chord length
    half_len = (B - A).norm() / 2.0

    # Circumradius from chord formula
    R = half_len / math.sin(theta / 2.0)

    # Unit perpendicular direction to chord (consistent choice)
    perp_dir = (A - B).perp().unit()

    # Distance from midpoint to center
    OM = R * math.cos(theta / 2.0)

    # Center
    O = M + perp_dir * OM

    # Output vertices 1..N in order
    out = []
    for i in range(1, N + 1):
        # Clockwise => negative rotation
        ang = -2.0 * math.pi * (i - N1) / N
        Pi = O + (A - O).rotate(ang)
        out.append(f"{Pi.x:.6f} {Pi.y:.6f}")

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

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

If you want, I can also add a short note about why the chosen sign for the center/perpendicular works with the clockwise rotation (and what to do if an alternative implementation produces mirrored output).