| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
ac了,讲一下我的方法这题的测试数据输入的点编号就是1--N,很方便我们处理。
我用的是枚举点,从1---N,枚举过的点不应该再遍历到;
每次尽量找偏左的方向上的点,如果依次遍历的是1,2,3,那么向量a23逆时针到a21的角度
是最小的,下面是用atan2计算逆时针旋转角度。
double angle(int x1,int y1,int x2,int y2)//顺序遍历点1,2,3,计算向量 a23(x2,y2)逆时针转向 a21(x1,y1)的角度
{
double a1=atan2((double)y1,(double)x1);
double a2=atan2((double)y2,(double)x2);
if(a2-a1>0)
return 2*PI-(a2-a1);
else
return -(a2-a1);
}
最后:
一、当最先遍历的是1,2,那么终止的时候还能遍历1,再遍历到2
二、你的遍历必须保证为真正的逆时针, 因为有时尽量找到偏左的点也能得出
顺时针,这样会出现重复或内边,怎样保证为真正的逆时针,把遍历时每次得出的角度加起来,
结果为多边形内角和即可(注意精度),任意多边形内角和公式(n-2)*PI。
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator