Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

ac了,讲一下我的方法

Posted by LiYiLong at 2013-10-06 19:25:32 on Problem 1092 and last updated at 2013-10-07 13:05:23
这题的测试数据输入的点编号就是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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator