# APCS實作題2022年10月第1題：巴士站牌

> 日期：2023年9月25日
> 作者：王一哲
> 題目來源：111年10月實作題第1題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=i428)

<br />

## 題目

### 問題描述

平面上有 $n$ 個巴士站，第 $i$ 個巴士站的位置可以用座標點 $(x_i, y_i)$ 來表示。

兩個巴士站之間行進的時間是這兩個巴士站座標的曼哈頓距離。曼哈頓距離的定義如下：
對於兩個座標點 $(x_1, y_1)$ 與 $(x_2, y_2)$，兩點之間曼哈頓距離的為 $| x_1 - x_2 | + | y_1 - y_2|$。

你今天要從的巴士站 $1$ 坐車到巴士站 $n$，中間依序經過巴士站 $2, 3, 4, \dots, (n-1)$。

請計算過程中相鄰兩站的行進時間的**最大值**與**最小值**。
<br />

### 輸入說明

第 $1$ 行有一個正整數 $n$ 表示路程中總共會經過幾個巴士站。
在輸入的第 $2$ 行到第 $n+1$ 行，每行有兩個整數標示巴士站的座標。
嚴格的說，輸入第 $i+1$ 行的兩個數字依序是 $x_i$ 和 $y_i$。

子題配分：
- 60%：$n = 4$ 且 $-100 \leq x_i, y_i \leq 100$
- 40%：$4 \leq n \leq 100$ 且 $-100 \leq x_i, y_i \leq 100$

<br />

### 輸出說明

在一行輸出兩個整數並以空格分開。
第一個整數表示相鄰兩站的行進時間的**最大值**。
第二個整數表示相鄰兩站的行進時間的**最小值**。

<br />

### 範例一：輸入

4
1 1
1 3
4 5
2 6

### 範例一：正確輸出

5 2

<br />

### 範例二：輸入

4
1 2
-1 -1
1 3
0 0

### 範例二：正確輸出

6 4

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 20 ms，使用記憶體最多約為 3.3 MB，通過測試。

n = int(input())  # 讀取站牌數量
minD, maxD = 10000, 0  # 儲存最短距離、最長距離用的變數
xp, yp = map(int, input().split())  # 讀取第1支站牌的位置

for _ in range(1, n):
    xc, yc = map(int, input().split())  # 依序讀取第2到n支站牌的位置
    dis = abs(xc - xp) + abs(yc - yp)  # 計算這支站牌與前一支站牌的距離
    minD = min(minD, dis)  # 更新最短距離
    maxD = max(maxD, dis)  # 更新最長距離
    xp, yp = xc, yc  # 更新前一支站牌的位置

print("{:d} {:d}".format(maxD, minD))  # 印出答案    

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 3 ms，使用記憶體最多約為 340 kB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;  // 讀取站牌數量
    int minD = 10000, maxD = 0;  // 儲存最短距離、最長距離用的變數
    int xp, yp, xc, yc, dis; cin >> xp >> yp;  // 讀取第1支站牌的位置

    for(int i=1; i<n; i++) {
        cin >> xc >> yc;  // 依序讀取第2到n支站牌的位置
        dis = abs(xc - xp) + abs(yc - yp);  // 計算這支站牌與前一支站牌的距離
        minD = min(minD, dis);  // 更新最短距離
        maxD = max(maxD, dis);  // 更新最長距離
        xp = xc; yp = yc;  // 更新前一支站牌的位置
    }
    cout << maxD << " " << minD << endl;  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`