<|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++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

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 coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

int n, n1, n2;
Point A, B;

void read() {
    cin >> n >> n1 >> n2;
    cin >> A >> B;
}

void solve() {
    // This problem isn't fundamentally hard. We are given the two coordinates
    // of the n1-th and n2-th point, so if we look at the AB line, we know the
    // center O lies on the line perpendicular to AB that passes through the
    // midpoint of AB. We also know the number of points between n1 and n2, so
    // we can figure out the angle AOB, which should be enough to get us the
    // exact location of O. Afterwards, we are mostly done - we already have the
    // radius of the circumscribed circle around the n-gon (distance between A
    // and O), so we can just get the evenly spaced n points on the circle.

    auto k = (n2 - n1 + n) % n;
    auto theta = 2.0 * Point::PI * k / n;

    auto mid = (A + B) / 2.0;
    auto half_len = (B - A).norm() / 2.0;
    auto R = half_len / sin(theta / 2.0);
    auto perp = (A - B).perp().unit();
    auto O = mid + perp * (R * cos(theta / 2.0));

    cout << fixed << setprecision(6);
    for(int i = 1; i <= n; ++i) {
        auto angle = -2.0 * Point::PI * (i - n1) / n;
        auto pt = O + (A - O).rotate(angle);
        cout << pt << '\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();
        solve();
    }

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