题目地址：Codeforces：Problem – 1C – Codeforces、洛谷：CF1C Ancient Berland Circus – 洛谷 | 计算机科学教育新生态

题目描述

Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

题意简述

给你一个正多边形中某三个点的坐标，求符合条件的最小正多边形的面积。保证答案中的正多边形边数不超过100。

输入输出格式

输入格式：
The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn’t exceed 1000 by absolute value, and is given with at most six digits after decimal point.

输出格式：
Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It’s guaranteed that the number of angles in the optimal polygon is not larger than 100.

输入输出样例

输入样例#1：

0.000000 0.000000
1.000000 1.000000
0.000000 1.000000

输出样例#1：

1.00000000

题解

给了三个点，正好能构成一个三角形。这个三角形肯定是正多边形的一部分，接下来考虑如何通过三角形内部的信息求出正多边形的信息。
考虑这个三角形的外接圆即是正多边形的外接圆，可以先把外接圆半径通过正弦定理求出来，即$\frac{a}{\sin A} = 2R \Rightarrow R = \frac{a}{2 \sin A}$。
有了外接圆半径后，我们可以求出三条边在外接圆中对着的圆心角，这可以通过余弦定理求出，即$cos \theta_a = \frac{2r^2-a^2}{2r^2} \Rightarrow \theta_a = \arccos(1-\frac{a^2}{2r^2})$。
考虑枚举多边形的边数，从而计算出多边形每条边对的圆心角，通过判断三条边对的圆心角是否是这个多边形圆心角的整数倍即可判断这三个点是否可以是这个正多边形的三个顶点。选择边数最少的正多边形即可求出最小的面积。
面积的求法，考虑把正$n$边形分成以外接圆圆形为顶点的$n$个小三角形，每个三角形的面积是$\frac{1}{2} R^2 \sin\frac{2\pi}{n}$，乘上边数$n$就得到了总面积。

理论上到此为止这个题已经做完了，但是你会发现直接这么写会WA。接下来是我在写的时候踩的坑，仅供读者参考：

1. 操作中精度误差比较大，EPS设置$10^{-6}$太小，需要调整到$10^{-4}$。
2. 如果直接利用余弦定理计算圆心角，容易遇到拿去算$\arccos$的值因为精度误差产生越界值，例如$-1$因为精度误差变成了$-1.00000000003$。考虑到三角形中边对的内角一定小于$\pi$，不会产生越界值，可以余弦定理算内角之后，利用内角是圆周角的性质，乘以2算出圆心角。这样做可以避免圆心角计算出一个nan的情况。

作为高考之后写的第一个练手题，这个题实在坑人，写了一下午2333

代码

// Code by KSkun, 2019/6
#include <cstdio>
#include <cmath>

#include <algorithm>

const double EPS = 1e-4;
const double PI = acos(-1);

inline int dcmp(double x) {
    if(fabs(x) < EPS) return 0;
    else return x < 0 ? -1 : 1;
}

struct Vector {
    double x, y;
    Vector operator+(const Vector &rhs) const {
        return Vector {x + rhs.x, y + rhs.y};
    }
    Vector operator-(const Vector &rhs) const {
        return Vector {x - rhs.x, y - rhs.y};
    }
};

inline double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

inline double length(Vector x) {
    return sqrt(dot(x, x));
}

inline double angle(Vector a, Vector b) {
    return acos(dot(a, b) / length(a) / length(b));
}

typedef Vector Point;

Point a, b, c;

inline bool checkInt(double x) {
    return dcmp(x - round(x)) == 0;
}

int main() {
    scanf("%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y);
    double al = length(b - c), bl = length(a - c), cl = length(a - b),
        r = cl / sin(angle(a - c, b - c)) / 2;
    double aan = acos((bl * bl + cl * cl - al * al) / 2 / bl / cl) * 2, 
        ban = acos((al * al + cl * cl - bl * bl) / 2 / al / cl) * 2,
        can = 2 * PI - aan - ban;
    for(int i = 3; i <= 100; i++) {
        double in = PI * 2 / i, c1 = aan / in, c2 = ban / in, c3 = can / in;
        if(!checkInt(c1) || !checkInt(c2) || !checkInt(c3) || round(c1 + c2 + c3) != i) continue;
        double s = r * r * sin(in) / 2 * i;
        printf("%.8lf", s); break;
    }
    return 0;
}