d847. 2D rank finding problem
Tags : BIT ST
Accepted rate : 198人/264人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 19:08

Content

二度空間上的排名計算問題(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。

設計一個程式,從檔案讀取點的名稱與座標,計算出在所給定的集合中,所有點的排名值。

Input

有多組測試資料

每組的第一行有一個數字N ( 1 ≦ N ≦ 10000 )

接下來會有N行,每行上會有兩個數字  x  y  ( 1 ≦ x , y ≦ 1000 )

Output

請按照輸入的順序,求出對於 ( x , y ) 有多少個點 ( a , b )

在它的左下方 a < x , b < y

Sample Input #1
5
961 404
640 145
983 888
539 71
437 532
Sample Output #1
2
1
4
0
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 2.0s , <10M
Hint :

Segment tree(ST)
Binary indexed tree(BIT)

Tags:
BIT ST
出處:
98學年度中投區資訊學科能力競賽 [管理者: morris1028 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」