d555. 平面上的極大點 - 高中生程式解題系統

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 #1

Sample Output #1

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:

排序

出處:

名題精選百則 [管理者： morris821028@gmail.com

morris1028(碼畜) ]