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 yygy at 2012-11-19 09:38:37 on Problem 1228
做法是判断每一边是除了两个顶点之外,还必须要有一个点在边的中间上面。
所有点构成直线的话输出NO
所以的话必须要>=6个点才行。
我的做法是先求凸包,
这里求凸包要注意一种情况,就是共线的点不能被包含进来,有一些凸包模版最后会有一个共线的点进来的
比如下面这个数据
一个正方形,每边上再加一个点
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0
要输出YES

然后我就枚举所有的边,再把原来的所有点枚举一遍,看看有没有点在这个边上,而且不是顶点。
我刚开始是用距离判断,一直WA,改用叉积就行了。

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