小明是個十分喜歡半夜飆車的人,由於要追求最大的刺激感,行進時的路線越是曲折他越喜歡,然而時間便是金錢,他並不希望走無謂的路去滿足他的慾望。而在某一日的下午,他在規劃晚上的路線,而地圖如下所示。
小明的目標為從起點(最左下之點)至終點(最右上之點)求出連續的線段組作為行車的依據,而取樣的結果如上圖所示。由於小明的偏好,他希望越靠近起點的線段斜率要盡可能的小且不能為負(可以為零),這樣在進入終點時才可以有帥氣的甩尾。請你寫一款程式幫助小明找出所採納的點。
第一行有一個正整數N (2 ≤ N ≤ 106),表示點的數量。第二至N行有N個非負整數對 (a1 , b1) … (aN, bN) 代表該點座標,並保證ai, bi都可以使用32 位元有號整數儲存而且保證b1 ≤ bN。
輸出所採納之座標點,並以x座標依序降冪排序。
8 1 3 2 2 3 4 4 6 6 5 5 4 4 2 2 5
1 3 5 4 6 5
3 1 1 2 2 3 3
1 1 2 2 3 3
4 0 0 1 1 2 0 3 1
0 0 2 0 3 1
4 0 0 1 0 2 0 3 3
0 0 1 0 2 0 3 3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|