SGU 120 SGU 228 Archipelago(计算几何)

Description:

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

Input:

In the first line of input there are $N,N1$N,N1 and $N2$N2 $(3\le N\le 150,1\le N1,N2\le N,N1\ne 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$N1 and $N2$N2 (one pair per line) with accuracy $4$4 digits after decimal point. Each coordinate is more than $-2000000$−2000000 and less than $2000000$2000000.

Output:

Write $N$N lines with coordinates for every island. Write coordinates in order of island numeration. Write answer with $6$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

题目链接

给出正 $n$n 边形第 $n1$n1 和 $n2$n2 个点，求多边形所有点

现求出正多边形重心 $O$O ，之后将向量 $\overrightarrow{Opoin{t}_{n1}}$Opointn1​ ​ 旋转 $n$n 次即可求出正多边形的所有点

先求出 $\overrightarrow{poin{t}_{n1}pointsn2}$pointn1​pointsn2 ​ 旋转到 $\overrightarrow{poin{t}_{n1}O}$pointn1​O ​ 所需角度 $rad$rad 进行旋转，之后将其向量长度改变为 $\frac{\frac{x}{2}}{\cos \left(rad\right)}$cos(rad)2x​​ 即可求出正多边形重心

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int maxn = 2e2 + 5;
const db eps = 1e-8;
const db pi = acos(-1.0);

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);}
db Format(db Key) {return Sgn(Key) == 0 ? (db)0 : Key;}
struct Point {db X, Y;};
typedef Point Vector;
bool operator == (Point Key1, Point Key2) {return Cmp(Key1.X, Key2.X) == 0 && Cmp(Key1.Y, Key2.Y) == 0;}
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;}
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;}
Vector operator * (Vector Key1, db Key2) {return (Vector){Key1.X * Key2, Key1.Y * Key2};}
Vector operator / (Vector Key1, db Key2) {return (Vector){Key1.X / Key2, Key1.Y / Key2};}
db GetLen(Vector Key) {return sqrt(Key * Key);}
db DisPointToPoint(Point Key1, Point Key2) {return GetLen(Key2 - Key1);}
Point Rotate(Point Key, db Angle) {return (Point){Key.X * cos(Angle) - Key.Y * sin(Angle),Key.X * sin(Angle) + Key.Y * cos(Angle)};}
Vector Rotate90(Vector Key) {return (Vector){-Key.Y, Key.X};}
struct Line {Point S, T;};
typedef Line Segment;
Point Cross(Line Key1, Line Key2) {
    db Temp = ((Key1.S - Key2.S) ^ (Key2.S - Key2.T)) / ((Key1.S - Key1.T) ^ (Key2.S - Key2.T));
    return (Point){Key1.S.X + (Key1.T.X - Key1.S.X) * Temp, Key1.S.Y + (Key1.T.Y - Key1.S.Y) * Temp};
}

int N, N1, N2;
db Angle, Rad;
Point points[maxn];
Point Center;

int main(int argc, char *argv[]) {
    scanf("%d%d%d", &N, &N1, &N2);
    scanf("%lf%lf", &points[N1].X, &points[N1].Y);
    scanf("%lf%lf", &points[N2].X, &points[N2].Y);
    if (N1 > N2) swap(N1, N2);
    Rad = (pi - (db)min(N2 - N1, N + N1 - N2) * 2.0 * pi / (db)N) / 2.0;
    if (N2 - N1 == N + N1 - N2) Center = (points[N1] + points[N2]) / 2.0;
    else if (N2 - N1 < N + N1 - N2) Center = Rotate(points[N2] - points[N1], -Rad) / 2.0 / cos(Rad) + points[N1];
    else Center = Rotate(points[N2] - points[N1], Rad) / 2.0 / cos(Rad) + points[N1];
    int Cur = (N1 - 1) == 0 ? N : (N1 - 1), k = 1; Angle = 2.0 * pi / (db)N;
    while (Cur != N1) {
        if (Cur == N2) {
            Cur--; k++;
            if (Cur == 0) Cur = N;
            continue;
        }
        points[Cur] = Rotate(points[N1] - Center, Angle * (db)k) + Center;
        Cur--; k++;
        if (Cur == 0) Cur = N;
    }
    for (int i = 1; i <= N; ++i) printf("%.6lf %.6lf\n", Format(points[i].X), Format(points[i].Y));
    return 0;
}