学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4195

题目意思，给定你一个正多边形上三个顶点，让你求这个正多边形最小有多少顶点！

其实题目很简单，就是精度有点不好控制，反正最多点就1000个，那么从小到大判断一下

按照角度来判断，注意取整方法和精度控制；多边形的心就是三角形的外心

#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <iostream>
using namespace std;
const double PI=acos(-1.0);
#define eps 1e-7
#define zero(a) (fabs(a)<eps?1:0)
struct point{
    double x,y;
}a,b,c,center,temp;
struct line{
    point a,b;
};
double cross(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point intersection(line u,line v){
    point ret=u.a;
    double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
    ret.x+=(u.b.x-u.a.x)*t;
    ret.y+=(u.b.y-u.a.y)*t;
    return ret;
}
point circumcenter(point a,point b,point c){
    line u,v;
    u.a.x=(a.x+b.x)/2;
    u.a.y=(a.y+b.y)/2;
    u.b.x=u.a.x-a.y+b.y;
    u.b.y=u.a.y+a.x-b.x;
    v.a.x=(a.x+c.x)/2;
    v.a.y=(a.y+c.y)/2;
    v.b.x=v.a.x-a.y+c.y;
    v.b.y=v.a.y+a.x-c.x;
    return intersection(u,v);
}
double dis(point &a,point &b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool is_ok(double a,double b,int &num){
    double t=a/b;
    if(zero(t)) return true;
    num+=int(t);
    t=t-int(t);
    if(t>=0.5)num++;
    if(t<0.5) return zero(t);
    else return zero(1.0-t);
}
char str[200];
int main(){
    int i,j,k,num;
    double len1,len2,len3,angle1,angle2,angle3,t;
    while(gets(str)){
        if(str[0]=='E')return 0;
        sscanf(str,"%lf%lf",&a.x,&a.y);
        gets(str);
        sscanf(str,"%lf%lf",&b.x,&b.y);
        gets(str);
        sscanf(str,"%lf%lf",&c.x,&c.y);
        center=circumcenter(a,b,c);
        len1=dis(a,b);
        len2=dis(a,c);
        len3=dis(b,c);
        if(len1>len2 && len1>len3){
            temp=a;a=c;c=temp;
        }
        else if(len2>len1 && len2>len3){
            temp=a;a=b;b=temp;
        }
        len1=dis(a,b);
        len2=dis(b,center);
        len3=dis(a,center);
        angle1=acos((len3*len3+len2*len2-len1*len1)/(len2*len3*2));
        len1=dis(a,c);
        len2=dis(center,a);
        len3=dis(center,c);
        angle2=acos((len3*len3+len2*len2-len1*len1)/(len2*len3*2));
        angle3=PI*2-angle1-angle2;
        if(zero(angle1-angle2) && zero(angle2-angle3)){
            printf("3\n");
            continue;
        }
        for(i=4;i<1000;i++){
            t=PI*2/i;
            num=0;
            if(is_ok(angle1-t,t,num)&&is_ok(angle2-t,t,num)&&is_ok(angle3-t,t,num)){
                if(num+3==i)
                    break;
            }
        }
        printf("%d\n",i);
    }
    return 0;
}