竹園論壇

標題: [排序]1205 - 直角三角形 [打印本頁]

作者: Sylveon 時間: 2015-2-24 20:19
標題: [排序]1205 - 直角三角形
原題：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]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)