本文主要是介绍Codeforces 1C. Ancient Berland Circus（计算几何:正多边形性质+高精度），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出三个点的坐标，输出含这三个点的最小正多边形面积
感觉这个题太牛逼了。。。
做的我元气大伤，昨晚看的题，一直没有思路
就去找了道类似的计算几何题Uva12300来做，做得还是挺顺手的
后来意识到了正多边形的一个性质：正n边形中一条边对应的圆心角为2×PI/n
以这里为突破口，先找出n的值，进而再求解
但有一个问题就是给定的点不一定相邻
也就是说两个点与圆心所对应的夹角有可能是多条边所对应的角
这里就是难点所在了
很容易相出求出3个点与圆心组成的3个角
然后对这3个点求最大公约数即为一条边所对应的圆心角
坑就在于角度是个浮点数，一点点误差久会导致最后求得的最大公约数错的离谱
我的做法是现设这三个角度为ang0 ang1 ang2
然后以每个角为一条边求出对应正多边形边数n[i]
再求出三个n值的最小公倍数！
这里的最小公倍数不能直接用乘除做
因为题目中说了最多不会超过正1000边形
所以我的做法是从3开始遍历直到1000
暴力判断这个值是否为3个数的倍数，若是即为最小公倍数
描述起来比较混乱。。。。
直接上代码吧。。。纯手打，真是醉了。。。
我的eps取的是1e-2，取1e-1跪在了第15个样例
代码如下：
/* ***********************************************
Author : yinwoods
E-Mail : yinwoods@163.com
Created Time : 2014年12月13日 星期六 17时00分47秒
File Name : 1C.cpp
************************************************ */#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 10010
#define eps 1e-2
#define LL long long
using namespace std;struct Point {double x, y;Point () {}Point (double _x, double _y) {x = _x;y = _y;}
};struct Line {double a, b, c;
};Line getLine(Point p1, Point p2) {Line line;Point mid((p1.x+p2.x)/2.0, (p1.y+p2.y)/2.0);if(p1.y == p2.y) {line.b = 0;line.a = 1.0;line.c = -mid.x;} else {line.b = 1.0;line.a = (p1.x-p2.x)/(p1.y-p2.y);line.c = -line.a*mid.x-line.b*mid.y;}return line;
}Point get_base(Line l1, Line l2) {Point ans;if(l1.b==0 || l2.b==0) {if(l1.b == 0) {ans.x = -l1.c/l1.a;ans.y = (-l2.c-l2.a*ans.x)/l2.b;return ans;}if(l2.b == 0) {ans.x = -l2.c/l2.a;ans.y = (-l1.c-l1.a*ans.x)/l1.b;return ans;}} else {ans.x = (l1.b*l2.c-l2.b*l1.c)/(l1.a*l2.b-l2.a*l1.b);ans.y = (-l1.c-l1.a*ans.x)/l1.b;return ans;}
}double dist(Point p1, Point p2) {return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}LL gcd(LL a, LL b) {return b ? gcd(b, a%b) : a;
}int main() {int num;double n[5];double ang[5];double lens[5];Point p1, p2, p3;scanf("%lf%lf", &p1.x, &p1.y);scanf("%lf%lf", &p2.x, &p2.y);scanf("%lf%lf", &p3.x, &p3.y);Line l1 = getLine(p1, p2);//求出中垂线方程Line l2 = getLine(p2, p3);Point bpoint = get_base(l1, l2);//找到圆心//printf("%.2lf\t%.2lf\n", bpoint.x, bpoint.y);//ang = 2*PI/n;double radius = dist(bpoint, p1);//对应外接圆半径lens[0] = dist(p1, p2)/2.0;lens[1] = dist(p2, p3)/2.0;lens[2] = dist(p3, p1)/2.0;for(int i=0; i<3; ++i) {ang[i] = asin(lens[i]/radius);//求出该边所对的圆心角n[i] = (2*acos(-1.0)/(ang[i]*2.0));//若以ang[i]为一条边对应圆心角，得正n[i]边形}bool ok[4];for(num=3; num<=1000; ++num) {//暴力找出最小公倍数ok[0] = ok[1] = ok[2] = false;for(int i=0; i<3; ++i) {double tmp1 = num/n[i];int tmp2 = tmp1+0.5;if(fabs(tmp1-tmp2) < eps) {ok[i] = true;}//printf("%lf\n", fabs(tmp1-tmp2));}if(ok[0] && ok[1] && ok[2])break;}int nn[4];for(int i=0; i<3; ++i)nn[i] = (int)(n[i]+0.5);//printf("num = %d\n", num);double angs = ang[0]/((int)(num/n[0]+0.5));double a = radius*sin(angs)*2.0;double r = radius*cos(angs);double res = num*a*r/2.0;//正多边形面积公式S = n个小三角形面积之和
/*printf("angle : %.2lf\t%.2lf\t%.2lf\n", ang[0], ang[1], ang[2]);//printf("对应边数：%d\t%d\t%d\n", n[0], n[1], n[2]);printf("对应边数：%.2lf\t%.2lf\t%.2lf\n", n[0], n[1], n[2]);printf("lens0 = %.2lf\tlens1 = %.2lf lens2 = %.2lf\n", lens[0], lens[1], lens[2]);printf("%d边形\n", num);
*/printf("%lf\n", res);return 0;
}这篇关于Codeforces 1C. Ancient Berland Circus（计算几何:正多边形性质+高精度）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
