当前位置: 代码迷 >> 综合 >> CF1C Ancient Berland Circus
  详细解决方案

CF1C Ancient Berland Circus

热度:67   发布时间:2023-12-02 14:39:44.0

题目:

现在所有的马戏团在 Berland 都有一个直径13米的圆形竞技场, 但在过去的事情是不同的。
在古代 Berland 竞技场的马戏团被塑造成一个规则 (等角) 多边形, 角色的大小和角度可能因马戏团而异。竞技场的每个角落都有一根特别的柱子, 柱子之间的绳子标记着竞技场的边缘。
最近, 来自 Berland 的科学家发现了古代马戏团竞技场的遗迹。他们发现只有三根柱子, 其他的被毁坏了
你得到了这三根柱子的坐标。请找出竞技场中最小的区域。
输入三行,每行包含两个数字,表示柱子的坐标,坐标的绝对值不超过1000,小数点后不超过6位。
输出古代竞技场的可能的最小区域面积,精确到小数点后至少6位,保证在最佳答案中多边形角的数目不大于100。

解决:

因为三个点是等角多边形的点,所以,这个三角形的外接圆也就是等角多边形的外接圆。
我们可以通过海伦公式+正弦定理得到三角形外接圆的半径。
然后,我们求出三条边作为原的弦多对应的圆心角,然后求出三个角度最大公约数的圆心角的角度。我们可以将多边形切割为若干个三角 形,而我们求得最大公约数的角度可以作为一份面积,求出三角形面积,然后乘上他的份数就是答案了。

代码:

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-2, PI = acos(-1);
struct Node{
    double x, y;
}aa, bb, cc;
double get(Node a, Node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double theta(double len, double r)
{
    double cs = (2 * r * r - len * len) / (2 * r * r);return acos(cs);
}
double gcd(double a, double b)
{
    // return b == 0 ? a : gcd(b, a % b);if (fabs(b) < eps) return a;if (fabs(a) < eps) return b;return gcd(b, fmod(a, b));
}
int main()
{
    cin >> aa.x >> aa.y >> bb.x >> bb.y >> cc.x >> cc.y;double a, b, c;a = get(bb, cc);b = get(aa, cc);c = get(aa, bb);double p = (a + b + c) / 2;double s = sqrt(p * (p - a) * (p - b) * (p - c));double r = a * b * c / (4 * s);// cout << r << endl;double A, B, C;A = theta(a, r);B = theta(b, r);C = theta(c, r);// C = PI * 2 - A - B;double d;d = gcd(A, B);d = gcd(d, C);// cout << d << endl;// cout << 2 * acos(-1) / d << endl;double ans = r * r * sin(d) * acos(-1) / d;printf("%.6lf\n", ans);return 0;
}