f764. 賽車 (Race)
標籤 :
通過比率 : 16人/30人 ( 53% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

輸入說明

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

輸出說明

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

範例輸入 #1
8
1 3
2 2
3 4
4 6
6 5
5 4
4 2
2 5
範例輸出 #1
1 3
5 4
6 5
範例輸入 #2
3
1 1
2 2
3 3
範例輸出 #2
1 1
2 2
3 3
範例輸入 #3
4
0 0
1 1
2 0
3 1
範例輸出 #3
0 0
2 0
3 1
範例輸入 #4
4
0 0
1 0
2 0
3 3
範例輸出 #4
0 0
1 0
2 0
3 3
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
出處:
TOI練習賽202012潛力組第二題 [管理者: fire5386 (becaidorz) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」