「CF1C Ancient Berland Circus」

CF第一场比赛的最后一题居然是计算几何.

这道题的考点也是比较多,所以来写一篇题解.

前置芝士

1. 平面直角坐标系中两点距离公式:\(l=\sqrt{(X_1-X_2)^2+(Y_1-Y_2)^2}\)
2. 海伦公式:在知道三边时用于计算三角形面积\(S=\sqrt{p(p-a)(p-b)(p-c)}\)(其中\(a,b,c\)为三角形三边,\(p=\frac{a+b+c}{2}\))
3. 外接圆半径公式:\(R=\frac{abc}{4S}\)
4. 解三角形
   
   (知道三边求角度):
   
   \(\cos B=\frac{a^2+c^2-b^2}{2ac}\)
   
   \(\cos A=\frac{b^2+c^2-a^2}{2bc}\)
   
   \(\cos C=\frac{a^2+b^2-c^2}{2ab}\)
   
   再将\(\cos A,\cos B,\cos C\)带入\(\arccos()\)求出角度
   
   (知道两边一夹角求第三边)
   
   \(c=\sqrt{a^2+b^2-2ab\cos C}\)
5. 欧几里得算法(gcd):看起来和这题没什么关系,具体后面会讲到.

具体做法

先看一张图:



在图中的A,B,C为给出的点,可以发现这个正多边形与这个三角形的外接圆相同,圆心为O,AO=BO=CO,知道外接圆半径公式后可以求出AO,BO,CO,在会解三角形后可以得出\(\angle AOB\),\(\angle BOC\),以及\(\angle AOC\)(指图中大于\(180^\circ\)的那个角).可以发现这三个角存在一定的数量关系,及这三个角都可以表示为一个角的整数倍,及相邻黄色半径的夹角,设这个角为\(\angle\alpha\),于是图中的\(\angle AOB=3*\angle\alpha\),\(\angle BOC=2*\angle\alpha\),\(\angle AOC=6*\angle\alpha\),于是\(\angle\alpha=gcd(\angle AOB,gcd(\angle BOC,\angle AOC))\),角度知道后对于每个小三角形的三边都知道了,三角形个数也知道了,就可以求出总面积了.

代码

#include<bits/stdc++.h>

using namespace std;

const double pi=3.1415926;

double mod(double a,double b)//小数取模

{

	return a-(int)(a/b)*b;

}

double gcd(double x,double y)//小数gcd

{

	if(y<=0.0001)return x;

	return gcd(y,mod(x,y));

}

double x,y,x2,y2,x3,y3;

int main()

{

	scanf("%lf%lf%lf%lf%lf%lf",&x,&y,&x2,&y2,&x3,&y3);

	//计算三角形三条边长

	double a=sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));

	double b=sqrt((x-x3)*(x-x3)+(y-y3)*(y-y3));

	double c=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));

	double p=(a+b+c)/2;

	double r=(a*b*c)/(4*sqrt(p*(p-a)*(p-b)*(p-c)));//通过r=(abc)/(4s)得出外接圆半径

	//分别求出以三条边为低，外接圆半径为腰的三角形的顶角角度

	double angle1=acos(1-(a*a)/(2*r*r));

	double angle2=acos(1-(b*b)/(2*r*r));

	double angle3=2*pi-angle1-angle2;

	double angle=gcd(angle1,gcd(angle2,angle3))/pi*180;//题目所示的以正多边形边长为低接圆半径为腰的三角形的顶角角度

	double side=sqrt(2*r*r-2*r*r*cos(angle/180*pi));//求出正多边形的边长

	double P=(r*2+side)/2;

	double S=sqrt(P*(P-r)*(P-r)*(P-side))/*三角形面积*/*(360/angle)/*三角形个数*/;//计算面积

	printf("%.6lf",S);//保留6位小数输出

	return 0;

}