CF1 Ancient Berland Circus

CF1 Ancient Berland Circus

Ancient Berland Circus


我的第一道计算几何题，这题的正确思路是：
先求出给出区域的三条边，根据海伦公式求出三角形面积。
根据余弦定理可求外接圆圆的半径r=(abc)/4s
求出每一条边对应的圆心角
求出每个圆心角的最大公约数q
可以得到最多有n=(2pi)/q份三角形，而每一份三角形的面积为1/2rrsin(q)，相乘即为答案

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(a) cout<<#a<<"="<>x1>>Y1>>x2>>y2>>x3>>y3;
    //求边长
	d1=count(x1-x2,Y1-y2);
	d2=count(x3-x2,y3-y2);
	d3=count(x1-x3,Y1-y3);
	//求面积
    p=(d1+d2+d3)/2;
    s=sqrt(p*(p-d1)*(p-d2)*(p-d3));
	r=d1*d2*d3/(4*s);

	//求弧度
	a1=acos(1-d1*d1/(2*r*r));
	a2=acos(1-d2*d2/(2*r*r));
	a3=2*pi-a1-a2;
	//最大公约数
	q=gcd(a1,gcd(a2,a3));

	// n=2*pi/q;
	// s1=0.5*r*r*sin(q);
	n*s1即为答案
    printf("%.10lfn",pi/q*r*r*sin(q));
    return 0;
}

一开始我没想到这么精巧的办法，直接暴力解方程算出圆心位置，然后直接算半径rr=(x-x1)(x-x1)+(y-y1)(y-y1);以及各边边长，也是根据余弦定理算出弧度。
不过最后发现有总有几位的精度跟不上，找了很久，问题很离谱：
gcd中b<0.001，如果改成0.00001或者更加精确的值，最后的结果误差反而更大。
第三个弧度不能直接算，只能用2pi-a1-a2得到，这里倒是好解释。
最后，记录一下求解圆心方程的一般公式：

设圆上三点为x1,y1, x2,y2, x3,y3
则可得（x-x1) ^ 2+(y-y1) ^ 2=（x-x2) ^ 2+(y-y2) ^ 2
（x-x1) ^ 2+(y-y1) ^ 2=（x-x3) ^ 2+(y-y3) ^ 2

两方程化简合并
得 A1x+B1y+C=0
A2x+B2y+C=0
其中：

A1=2*(x2-x1);
B1=2*(y2-y1);
C1=x1*x1-x2*x2+y1*y1-y2*y2;

A2=2*(x3-x1);
B2=2*(y3-y1);
C2=x1*x1-x3*x3+y1*y1-y3*y3;

最后：

x=(B2*C2-B2*C1)/(A1*B2-A2*B1);
y=(A1*C2-A2*C1)/(A2*B1-A1*B2);
double r2=(x-x1)*(x-x1)+(y-y1)*(y-y1);    

不过算半径还得是余弦定理，比这样硬算方便多了