首页 > 代码库 > codeforces Round #1 C题 Ancient Berland Circus (计算几何)

codeforces Round #1 C题 Ancient Berland Circus (计算几何)

这题的思路很好想,分成以下4步:

1:求外切园半径

2:求三个圆心角

3:求三个圆心角的最大公约数

4:最大公约数就是最大的正多边形内角,求面积即可。

但是每一步都不会求啊。。。。sad。。。当想到第3步的时候甚至觉得应该用别的方法来求。。要换方法。。几何太渣了。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=100000000;
const int INF=0x3f3f3f3f;
const double eqs=0.01;
struct Point
{
    double x, y;
}p[4];
bool dmp(double x, double y)
{
    return fabs(x-y)<eqs;
}
double fgcd(double x, double y)
{
    if(dmp(x,0)) return y;
    if(dmp(y,0)) return x;
    return fgcd(y,fmod(x,y));
}
double dist(Point f1, Point f2)
{
    return sqrt((f1.x-f2.x)*(f1.x-f2.x)+(f1.y-f2.y)*(f1.y-f2.y));
}
int main()
{
    double s, r, ang[4], d[4], pp, angle;
    int i;
    for(i=0;i<3;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    for(i=0;i<3;i++){
        d[i]=dist(p[i],p[(i+1)%3]);
    }
    pp=(d[0]+d[1]+d[2])/2.0;
    s=sqrt(pp*(pp-d[0])*(pp-d[1])*(pp-d[2]));
    r=d[0]*d[1]*d[2]/(4*s);
    ang[0]=acos(1-d[0]*d[0]/(2*r*r));
    ang[1]=acos(1-d[1]*d[1]/(2*r*r));
    ang[2]=2*pi-ang[0]-ang[1];
    angle=fgcd(ang[0],ang[1]);
    angle=fgcd(angle,ang[2]);
    printf("%.6f\n",r*r*pi*sin(angle)/angle);
    return 0;
}


codeforces Round #1 C题 Ancient Berland Circus (计算几何)