1 条题解
-
0
我们需要找到三个点所在的具有最少顶点数的正多边形。正多边形的顶点均匀分布在圆周上,因此三个点之间的夹角必须是360度的整数分之一。具体步骤如下:
1、计算三个点之间的边长:计算三个点两两之间的距离。 2、计算外接圆半径:使用三角形外接圆公式计算半径。 3、计算中心角:通过余弦定理计算三个点之间的中心角。 4、验证多边形顶点数:检查中心角是否为360度的整数分之一,并找到最小的满足条件的n。
#include <iostream> #include <cmath> #include <vector> #include <algorithm> #include <cstdio> using namespace std; const double EPS = 1e-6; const double PI = acos(-1.0); struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; double dist(Point a, Point b) { return hypot(a.x - b.x, a.y - b.y); } double cross(Point o, Point a, Point b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); } Point circumcenter(Point a, Point b, Point c) { double D = 2 * ( (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) ); double Ux = ( ( (a.x - c.x) * (a.x + c.x) + (a.y - c.y) * (a.y + c.y) ) * (b.y - c.y) - ( (b.x - c.x) * (b.x + c.x) + (b.y - c.y) * (b.y + c.y) ) * (a.y - c.y) ) / D; double Uy = ( ( (b.x - c.x) * (b.x + c.x) + (b.y - c.y) * (b.y + c.y) ) * (a.x - c.x) - ( (a.x - c.x) * (a.x + c.x) + (a.y - c.y) * (a.y + c.y) ) * (b.x - c.x) ) / D; return Point(Ux, Uy); } double angle(Point o, Point a, Point b) { double oa = dist(o, a), ob = dist(o, b), ab = dist(a, b); double cosTheta = (oa * oa + ob * ob - ab * ab) / (2 * oa * ob); return acos(cosTheta); } int solve(Point a, Point b, Point c) { Point o = circumcenter(a, b, c); double r = dist(o, a); double angle1 = angle(o, a, b); double angle2 = angle(o, b, c); double angle3 = angle(o, a, c); vector<double> angles; angles.push_back(angle1); angles.push_back(angle2); angles.push_back(angle3); for (int n = 3; n <= 200; ++n) { bool ok = true; for (int i = 0; i < 3; ++i) { double theta = angles[i] * n / (2 * PI); if (fabs(theta - round(theta)) > EPS) { ok = false; break; } } if (ok) return n; } return -1; } int main() { int n; cin >> n; while (n--) { Point a, b, c; cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y; cout << solve(a, b, c) << endl; } return 0; }
- 1
信息
- ID
- 1336
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者