f764: 賽車 (Race)
Tags :
Accepted rate : 12人/14人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-22 22:35

Content

小明是個十分喜歡半夜飆車的人,由於要追求最大的刺激感,行進時的路線越是曲折他越喜歡,然而時間便是金錢,他並不希望走無謂的路去滿足他的慾望。而在某一日的下午,他在規劃晚上的路線,而地圖如下所示。

小明的目標為從起點(最左下之點)至終點(最右上之點)求出連續的線段組作為行車的依據,而取樣的結果如上圖所示。由於小明的偏好,他希望越靠近起點的線段斜率要盡可能的小且不能為負(可以為零),這樣在進入終點時才可以有帥氣的甩尾。請你寫一款程式幫助小明找出所採納的點。

Input

第一行有一個正整數N (2 ≤ N ≤ 106),表示點的數量。第二至N行有N個非負整數對 (a1 , b1) … (aN, bN) 代表該點座標,並保證ai, bi都可以使用32 位元有號整數儲存而且保證b1 ≤ bN

Output

輸出所採納之座標點,並以x座標依序降冪排序。

Sample Input #1
8
1 3
2 2
3 4
4 6
6 5
5 4
4 2
2 5
Sample Output #1
1 3
5 4
6 5
Sample Input #2
3
1 1
2 2
3 3
Sample Output #2
1 1
2 2
3 3
Sample Input #3
4
0 0
1 1
2 0
3 1
Sample Output #3
0 0
2 0
3 1
Sample Input #4
4
0 0
1 0
2 0
3 3
Sample Output #4
0 0
1 0
2 0
3 3
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (5%): 3.0s , <1K
不公開 測資點#1 (5%): 3.0s , <1K
不公開 測資點#2 (5%): 3.0s , <10M
不公開 測資點#3 (5%): 3.0s , <50M
不公開 測資點#4 (5%): 3.0s , <1M
不公開 測資點#5 (5%): 3.0s , <1M
不公開 測資點#6 (5%): 3.0s , <10M
不公開 測資點#7 (5%): 3.0s , <10M
不公開 測資點#8 (5%): 3.0s , <1M
不公開 測資點#9 (5%): 3.0s , <10M
不公開 測資點#10 (5%): 3.0s , <50M
不公開 測資點#11 (5%): 3.0s , <10M
不公開 測資點#12 (5%): 3.0s , <50M
不公開 測資點#13 (5%): 3.0s , <1M
不公開 測資點#14 (5%): 3.0s , <50M
不公開 測資點#15 (5%): 3.0s , <10M
不公開 測資點#16 (5%): 3.0s , <1K
不公開 測資點#17 (5%): 3.0s , <10M
不公開 測資點#18 (5%): 3.0s , <10M
不公開 測資點#19 (5%): 3.0s , <50M
Hint :
Tags:
出處:
TOI練習賽202012潛力組第二題 [管理者:
fire5386 (皮卡丘)
]


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