a325. TOI 2020/12 潛力組：賽車

題目描述

給定平面上的 N 個點，小明想把其中一些點以連續線段接起來，從最左邊的點行駛到最右邊的點。原題希望越接近起點的線段，其斜率盡可能小，而且斜率不能是負數，可以等於零。請找出這條路線所採用的座標點。

原題示意圖的選點路線為 (1, 3) → (5, 4) → (6, 5)，與範例 1 的輸出相同。圖中其餘候選點包括 (2, 2)、(3, 4)、(4, 6)、(4, 2)、(2, 5)。此處用座標及連線次序重述圖意，官方解題投影片另明確說明：直線路段上經過的所有點都應保留。

輸入格式

第一行為正整數 N，表示點的數量。之後提供 N 組非負整數座標 (a1, b1)、…、(aN, bN)。原文將這一段寫成「第二至 N 行有 N 個非負整數對」；行數文字有衝突，三個官方範例均在第一行之後提供 N 行座標。

• 2 ≤ N ≤ 10^6
• ai、bi 皆為可用 32 位元有號整數儲存的非負整數，即 0 ≤ ai、bi ≤ 2147483647。
• 原題保證 b1 ≤ bN。

原題分組：10 分滿足 N ≤ 10；90 分無額外限制。

輸出格式

輸出採用的座標點，每行列出一個點的 x、y 座標，依 x 座標升冪排列；同一直線路段上經過的點都須保留。

官方資料校對與待釐清事項

本稿僅供待審，尚未建立完整隱藏測資。

• PDF 的「降冪」與三組範例矛盾；官方參考程式由左至右輸出，故本稿依官方程式與範例改為升冪，並揭露更正。
• 官方解題投影片明確要求保留直線路段上經過的所有點，釐清同斜率取捨。
• 原文輸入行數與第三組範例欄名有誤植；依全部範例與參考程式，第一行後有 N 行座標，第三組左欄是輸入。
• 多個相同座標或多個最左、最右點的完整規則仍未在題目文字中清楚定義；不將參考程式對未明示情況的行為當作新限制。

範例 1

輸入：

8
1 3
2 2
3 4
4 6
6 5
5 4
4 2
2 5

輸出：

1 3
5 4
6 5

範例 2

輸入：

3
1 1
2 2
3 3

輸出：

1 1
2 2
3 3

範例 3

輸入：

4
0 0
1 1
2 0
3 1

輸出：

0 0
2 0
3 1

來源

TOI 2020/12 練習賽潛力組〈賽車（Race）〉。本稿依官方 PDF 自行整理文字，保留原題未釐清處及全部官方範例。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202012/Race.pdf

官方解題投影片：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202012/Race.odp 官方參考程式：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202012/Race.zip