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