d555: 平面上的極大點
Tags : 排序
Accepted rate : 285人/340人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 14:35

Content

       在平面上如果有兩個點 ( x , y ) 與 ( a , b ),我們說 ( x , y ) 支配(Dominate)了
( a , b )這就是指 x ≧ a 而且 y ≧ b;用圖來看就是 ( a , b ) 座落在以 ( x , y ) 為右上角的
一點無的區域中。

       對於平面上的任意一個有限點集合而言,一定存在有若干個點,它們不會被
集合中的內一點所支配,這些個數就構成一個所謂的極大集合。請寫一個程式,
讀入一個新的集合,找出這個集合中的極大值。

    ※簡單的說  若找不到一點在 ( x , y ) 的右上方,則 ( x , y ) 就要輸出

Input

每個測資的第一行有一個數字 N ( 1 ≦ N ≦ 50,0000 ),代表接下來有N行,
每行上有兩個數字 x , y  ( 0 ≦ X,Y ≦ 100000 )
      分別代表一點的 X 軸座標,與 Y 軸座標。

Output

請依照 X 軸的大小,由小輸出至大,剩餘的請參考Sample Out

Sample Input
11
0 8
1 10
3 4
4 6
4 9
5 8
6 9
7 5
8 7
9 8
10 6 
Sample Output
Case 1:                               //第幾筆測資
Dominate Point: 4                     //點的個數
(1,10)
(6,9)
(9,8)
(10,6)
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <10M
公開 測資點#2 (20%): 2.0s , <10M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
Hint :

以上為測資的圖  大黑點即為輸出的點。 (左下角為(0,0))

Tags:
排序
出處:
名題精選百則 [管理者:
morris1028 (碼畜)
]


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