[問題] Uva 361 AC
看板Prob_Solve (計算數學 Problem Solving)作者tom1990 (湯姆祥)時間13年前 (2011/02/08 17:49)推噓2(2推 0噓 6→)留言8則, 1人參與討論串1/1
開發平台(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)
推
02/09 20:00, , 1F
02/09 20:00, 1F
→
02/09 20:01, , 2F
02/09 20:01, 2F
→
02/09 20:02, , 3F
02/09 20:02, 3F
→
02/09 20:02, , 4F
02/09 20:02, 4F
→
02/09 20:04, , 5F
02/09 20:04, 5F
→
02/09 20:05, , 6F
02/09 20:05, 6F
推
02/09 21:01, , 7F
02/09 21:01, 7F
→
02/09 21:02, , 8F
02/09 21:02, 8F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
