hdu_round1-1007 吃巧克力(计算几何)

记录一个菜逼的成长。。

吃巧克力

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 317 Accepted Submission(s): 38

Problem Description
CYF 喜欢吃巧克力，有一天，CYF收到了一份镶嵌在平面直角坐标系上的巧克力，这个巧克力的形状是一个正多边形。日子一天天过去，CYF吃完了这份巧克力，但是却忘记了自己吃的巧克力有几条边，只记得正多边形巧克力上三个点的坐标。
CYF知道送自己巧克力的人非常小气，所以正多边形巧克力的边数不会超过100。现在的CYF非常想知道自己吃的正多边形巧克力到底有多少条边，你能帮他算一下吗？

Input
每个样例包含一组输入。
一个输入有三行每行是一个点的坐标
Xi Yi
坐标之间用空格隔开

Output
输出CYF吃的巧克力最少有多少个角

Sample Input
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000

Sample Output
4

正n多边形的内角可以被当前点与不相邻的点的连线等分
假设有一个正六边形，如图所示，最小的角度为30度，其他的角度都是30度的倍数

考虑△ABC
假设已知三点的坐标为A,B,C
求出这个三角形的内角的$gcd = \frac {\pi} {6}$
正n多边形的内角是$r = \frac {\pi(n-2)} {n} = \pi - \frac {2\pi}{n}$
角B = $\pi - 2*gcd = r$
得到$n = \frac {\pi} {gcd}$

这里要用到浮点数求gcd

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
int INF = 0x3f3f3f3f;
const double pi = acos(-1);
struct Point{
    double x,y;
}a,b,c;
double fgcd(double a, double b) 
{  
    if (b < eps) return a;  
    return fgcd(b,fmod(a,b));  
}  
void solve(double rab,double rac,double rbc)
{
  double gcd = fgcd(rab,rac);
  gcd = fgcd(gcd,rbc);
  printf("%.0f\n",pi/gcd);
}
int main()
{
  int n;
  while(~scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y)){
    double aa = hypot(c.x-b.x,c.y-b.y);
    double bb = hypot(a.x-c.x,a.y-c.y);
    double cc = hypot(b.x-a.x,b.y-a.y);
    double A = acos((bb*bb+cc*cc-aa*aa) / (2*bb*cc));
    double B = acos((aa*aa+cc*cc-bb*bb) / (2*aa*cc));
    double C = acos((bb*bb+aa*aa-cc*cc) / (2*bb*aa));
    solve(A,B,C);
  }
  return 0;
}