作者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