UVa 10439 - Temple of Dune

链接

传送门

题意

给出三个点， 问这三个点最少是正几边形的顶点。

思路

之前组队赛做过，三个点在正多边形的外接圆，三个点的两两关于圆心的夹角是正多边形相邻两点圆心角的倍数，枚举正多边形的边数依次检验即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-5;
const double PI2 = acos(-1) * 2;
const int maxn = 5;
const int maxm = 1010;
double ANG[maxm];

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) : x(x), y(y) {}
} p[maxn];

typedef Point Vector;

Vector operator - (Vector a, Vector b) {
  return Vector(a.x - b.x, a.y - b.y);
}

int dcmp(double x) {
  if (fabs(x) < eps) {
    return 0;
  }
  return x > 0 ? 1 : -1;
}

double Dot(const Vector& A, const Vector& B) {
  return A.x * B.x + A.y * B.y;
}

double Length(const Vector& A) {
  return sqrt(Dot(A, A));
}

double Angle(const Vector& A, const Vector& B) {
  return acos(Dot(A, B) / Length(A) / Length(B));
}

bool check(double a, double mod) {
  a -= floor(a / mod) * mod;
  return dcmp(a) == 0 || dcmp(a - mod) == 0;
}

int main() {
  for (int i = 3; i < maxm; ++i) {
    ANG[i] = PI2 / i;
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    for (int i = 0; i < 3; ++i) {
      scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    double ang1 = 2 * Angle(p[0] - p[2], p[1] - p[2]);
    double ang2 = 2 * Angle(p[1] - p[0], p[2] - p[0]);
    double ang3 = 2 * Angle(p[2] - p[1], p[0] - p[1]);
    int ans = 0;
    for (int i = 3; i < maxm; ++i) {
      if (check(ang1, ANG[i]) && check(ang2, ANG[i]) && check(ang3, ANG[i])) {
        ans = i;
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}