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啊,说一下思路,做法是判断每一边是除了两个顶点之外,还必须要有一个点在边的中间上面。 所有点构成直线的话输出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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator