1 条题解

  • 0
    @ 2025-5-28 9:08:59

    我们需要找到三个点所在的具有最少顶点数的正多边形。正多边形的顶点均匀分布在圆周上,因此三个点之间的夹角必须是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
    上传者