查看: 796|回復: 0

[TIOJ] [排序]1205 - 直角三角形

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-2-24 20:19:17 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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] 本題沒說測資有多少... 反正就是過了

    053.PNG
    [sojcodepad]f5bf26e3[/sojcodepad]

    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表