TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題:http://tioj.ck.tp.edu.tw/problems/1205
AC:http://tioj.ck.tp.edu.tw/submissions/10046
我不大曉得這題如何分類,就把比較關鍵的一步拿來當作TAG了。
隨便想應該都能想出個[tex]O(N^3)[/tex]的爆解。這裡的想法是考慮直角三角形直角的兩個夾邊互相垂直(廢話),如果我們能拔一個點能產生出的所有斜率排序,那我們又能很快地找出另一互為垂直的斜率有幾個。
關鍵在於處理斜率,鉛直線和水平線如何處裡呢?索性定義一個分數類別 ( 其實就一直把pair拿來用 ) ,使水平線為[tex]{0,1}[/tex],鉛直線為[tex]{1,0}[/tex],然後稍微維護好資料就可以。ㄗㄨㄟ用sort+equal_range來到處加一加,最後答案要除以二 (一個三角形被算到兩邊) 排序後各操作複雜度為 [tex]O(N^2logN)[/tex] 本題沒說測資有多少... 反正就是過了
[sojcodepad]f5bf26e3[/sojcodepad]
|
|