Archipelago

题目描述

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