CF1C Ancient Berland Circus

这是一道计算几何题

题意是求包含给定三点的正多边形最小面积。

如果要求正多边形面积最小，明显正多边形的顶点都在给定三点构成的三角形外接圆上，如图

已知的是三角形三点坐标，借此可以求出三角形三边长，结合海伦公式S_{\Delta ABC}=\sqrt{p(p-a)(p-b)(p-c)}\ (p=\frac{a+b+c}{2})可以求得三角形面积。

可以证明S_{\Delta ABC}=\frac{ah_{a}}{2}=\frac{ab\sin C}{2}，结合正弦定理\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2R即可得出三角形外接圆半径R=\frac{abc}{4S_{\Delta ABC}}。

根据余弦定理分别求出三角形三边作为弦所对的圆心角的三角函数值，使用反三角函数求出圆心角的度数，由于圆心角的度数皆为正多边形中心角度数的倍数，可以通过求圆心角度数的最大公约数求出正多边形的中心角度数t，已知组成正多边形的三角形面积为S_{\Delta}=\frac{R^{2}\sin t}{2}，而这样的三角形有\frac{2\pi}{t}个，于是正多边形面积为\frac{\pi R^{2}\sin t}{t}。

#include<cstdio>
#include<cmath>
const double Pi=acos(-1.0);        //π的值
const double EPS=1E-2;            //控制精度
struct Point {
    double x,y;
}P[3];
double len[3],a[3];        //len为边长，a为圆心角角度。
double Get(int i,int j) {    //求两点之间距离
    return sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y));
}
double gcd(double a,double b) {    //double类型的最大公约数
    if(fabs(b)<EPS)
        return a;
    if(fabs(a)<EPS)
        return b;
    return gcd(b,fmod(a,b));    //fmod(a,b), double类型的取模
}
int main() {
    double t=0.0,A,r;
    for(int i=0;i<3;++i)
        scanf("%lf%lf",&P[i].x,&P[i].y);
    for(int i=0;i<3;t+=len[i],++i)
        len[i]=Get(i,(i+1)%3);
    t/=2;
    A=sqrt(t*(t-len[0])*(t-len[1])*(t-len[2]));    //求三角形面积
    r=len[0]*len[1]*len[2]/(4*A);                //求三角形外接圆半径
    for(int i=0;i<2;++i)
        a[i]=acos(1-len[i]*len[i]/(2*r*r));        //求圆心角度数
    a[2]=2*Pi-a[0]-a[1];                        //为防止误差，最后一个圆心角根据三角形三边作为弦所对的三个圆心角之和为360°求出
    t=gcd(a[0],gcd(a[1],a[2]));                    //求圆心角的最大公约数
    printf("%.6lf",(Pi*r*r*sin(t))/t);            //求正多边形面积
    return 0;
}