二度空間上的排名計算問題(2D rank finding problem):給定二度平面空間(2D)上的點A = (a1,a2)與點B = (b1,b2),其大小關係定義為若A > B 若且唯若 a1> b1 且 a2 > b2 ;亦即A點在B點的右上方。如下圖中,B >A, C>A, D>A, D>C, D> B。值得注意的是,並非任意兩點均可以決定大小關係,如下圖中的點A與點E,點D與點E等,無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x1,y1), (x2,y2), …, (xn,yn),定義某一個點的排名(rank) 為所給的點集合中,比該點小的點的個數。
如上圖中,rank(A)= 0, rank(B) = 1, rank(C) = 1, rank(D) = 3, rank(E) = 0。
設計一個程式,從檔案讀取點的名稱與座標,計算出在所給定的集合中,所有點的排名值。
有多組測試資料
每組的第一行有一個數字N ( 1 ≦ N ≦ 10000 )
接下來會有N行,每行上會有兩個數字 x y ( 1 ≦ x , y ≦ 1000 )
請按照輸入的順序,求出對於 ( x , y ) 有多少個點 ( a , b )
在它的左下方 a < x , b < y
5 961 404 640 145 983 888 539 71 437 532
2 1 4 0 0
Segment tree(ST)
Binary indexed tree(BIT)
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|