题目描述
Archipelago Ber-Islands consists of $N$ islands that are vertices of equiangular and equilateral $N$-gon. Islands are clockwise numerated. Coordinates of island $N_1$ are $(x_1, y_1)$, and island $N_2$ – $(x_2, y_2)$. Your task is to find coordinates of all $N$ islands.
题意概述
平面上有一个正$N$边形,它的顶点按顺时针方向依次标号。给定第$N_1$、$N_2$个点的坐标$(x_1, y_1)$、$(x_2, y_2)$,求所有顶点的坐标。
数据范围:$3 \le N \le 150, \; N_1 \neq N_2, \; |x_1|, |y_1|, |x_2|, |y_2| \le 2 \times 10^6$。
算法分析
可以先计算出圆心角,根据圆心角、三角函数和向量旋转计算出圆心坐标,之后就可以用向量旋转计算出所有顶点的坐标。
将$(x, y)$绕原点逆时针旋转$\theta$度得到$(x\cos(\theta)-y\sin(\theta), x\sin(\theta)+y\cos(\theta))$。
代码
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; static const double PI = acos(-1); static const double EPS = 1e-8; int cmp(double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; } struct Point { double x, y; Point(double _x = 0, double _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 * (const double &a) const { return Point(x * a, y * a); } Point operator / (const double &a) const { return Point(x / a, y / a); } double operator ! () const { return sqrt(x * x + y * y); } double operator & (const Point &p) const { return x * p.x + y * p.y; } double operator * (const Point &p) const { return x * p.y - y * p.x; } Point operator << (const double &a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); } }; struct Solver { private: static const int N = 160; int n, a, b; Point p, q, tmp, ans[N]; void input() { scanf("%d%d%d%lf%lf%lf%lf", &n, &a, &b, &p.x, &p.y, &q.x, &q.y); } void init() { if (a > b) swap(a, b), swap(p, q); double angle = 2 * PI / n * (b - a); if (cmp(PI - angle)) { tmp = p + (q - p) / 2 / cos((PI - angle) / 2); tmp = (tmp - p << (angle - PI) / 2) + p; } else tmp = p + (q - p) / 2; } void process() { for (int i = 1; i <= n; ++ i) ans[a] = p, a %= n, ++ a, p = (p - tmp << -2 * PI / n) + tmp; for (int i = 1; i <= n; ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }