作者tom1990 (汤姆祥)
看板Prob_Solve
标题[问题] Uva 361
时间Tue Feb 8 17:49:47 2011
开发平台(Platform): (Ex: VC++, GCC, Linux, ...)
GCC
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question)：
wrong answer
喂入的资料(Input)：
sample 和 forum 测资都正确
预期的正确结果(Expected Output)：
错误结果(Wrong Output)：
程式码(Code)：(请善用置底文网页, 记得排版)
http://paste.plurk.com/show/367351
补充说明(Supplement)：
题目：
http://0rz.tw/t5yHX
大意： 有一群警察、歹徒和民众，民众只要在三个警察包围下就是safe，若没有
被警察包围而被三个歹徒包围就是robbed，如果都没有则是neither。
警察、歹徒和民众至多200人，人是整数座标范围在[-500, 500]。
解法： 把警察的convex hall和歹徒的convex hall求出来并计算面积(我是用包下
再包上的方法围出凸包)，把民众丢进警察凸包看是否面积相等(如果警察不
能围成三角型则算民众在线段内否)，如果面积不变则表示民众有警察保护，
但是面积改变则再把民众丢到歹徒凸包中看是否面积不变，若不变就是robbed
，改变就是neither。
面积公式：0.5*sigma(i=1~n)(xi-1*yi - xi*yi-1) point n指原点
O(p*n*lg(n)) (p=citizens, n=MAX(cops, robbers))
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.167.138.220
※ 编辑: tom1990 来自: 218.167.138.220 (02/08 20:20)
※ 编辑: tom1990 来自: 218.167.138.220 (02/09 18:56)
1F：推 seanwu:判断在线段上的部份可能不太对，面积=0不代表只有两个点 02/09 20:00
2F：→ seanwu:可以所有点都在同一条直线上 02/09 20:01
3F：→ seanwu:所以...退化成一条线的三角形到底算不算..题目也没写的样子 02/09 20:02
4F：→ seanwu:话说"两点间的线段"，应该不是"三个警察"吧XD 02/09 20:02
5F：→ seanwu:顺便一题，这种题目要小心误差，以座标-500~500来看 02/09 20:04
6F：→ seanwu:用int会比较保险一点 02/09 20:05
7F：推 seanwu:抱歉刚刚没看仔细，原po的convex会把共线点去掉 02/09 21:01
8F：→ seanwu:一楼的推文请无视.. 确实是只会有两个点 02/09 21:02