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

时间:2023-02-10 20:20:53

这题的思路很好想,分成以下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;
}