# 2023/06 APCS 實作題

# 第一題 - 路徑偵測
:::info
https://zerojudge.tw/ShowProblem?problemid=k731
:::

## 題目
給一個二維平面，座標如同數學的二維座 標(Ｙ正為北，Ｘ正為東)。起始位置在 (0, 0)，接下來會有 $n$ 個座標，你需要按照這些座標點的順序移動，保證僅會垂直 或水平方向上移動，不會斜向移動，且第 一個點保證一定是Ｘ軸正的位置(初始方向向右)。
請輸出這條路徑中，左轉、右轉、迴轉的 個數分別為多少。
子問題一 (60%) $n = 2$
子問題二 (40%) $n \le 100$

## 輸入說明:
第一行輸入一個正整數 $n$，接下來有 $n$ 行，每一行都有兩個正整數 $x$, $y$。保證的是相鄰兩個點的座標差值不超過 $100$。

## 輸出說明:
輸出三個正整數，分別代表左轉、右轉、 迴轉的次數。
## 解題絲路
這題很明顯是在考 **`在平面上的外積應用`**， 詳情可以參考 [內外積在程式中的應用](/zTX5_h5xQmeloZhV9WJjnQ)
所以我們知道正負號可判斷旋轉方向：
* $> 0$ → 左轉
* $< 0$ → 右轉
* $= 0$ → 共線(迴轉或原地不動)

那這題就變簡單很多了，唯一要注意的是外積=0也可能是原地不動，要如何判斷是原地不動還是迴轉，要透過**內積**來判斷銳角還是鈍角
:::warning
兩向量夾角為鈍角($cos$鈍角<0)表示反方向
:::

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

struct Point {
    double x, y;
};

int main() {
    io;

    int left = 0, right = 0, straight = 0;
    int n;
    cin >> n;

    Point p[105];
    for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;

    for (int i = 2; i <= n; ++i) {
        int x1 = p[i-1].x - p[i-2].x; // 向量 AB
        int y1 = p[i-1].y - p[i-2].y;
        int x2 = p[i].x - p[i-1].x;   // 向量 BC
        int y2 = p[i].y - p[i-1].y;

        int dir = x1 * y2 - y1 * x2; // 外積

        if (dir > 0) left++;
        else if (dir < 0) right++;
        else if (dir== 0 && (x1*x2<0||y1*y2<0))straight++;
    }

    cout << left << " " << right << " " << straight;
}

# 第二題 - 特殊位置
:::info
https://zerojudge.tw/ShowProblem?problemid=k732
:::

## 題目
給定一個 $n \times m$ 的二維矩陣 a， 設 $x$ = a[i][j]，離 $(i, j)$ 曼哈頓距 離為 $x$ 內的點數值總和 % 10 恰為 $x$ 的稱之為特殊位置。定義兩個點 (a, b) 和 (c, d) 的曼哈頓距離為 |a - c| + |b - d|
請寫一個程式，輸出共有幾個特殊位置， 並按照字典序由小到大輸出這些位置的座 標。
子問題一 (60%) $n = 1$
子問題二 (40%) $n \le 50$, $m \le 50$

## 輸入說明:
第一行輸入兩個正整數 $n, m (1 \le n, m \le 50)$，接下來有 $n$ 行，每行有 $m$ 個數字，每一個數字介於 $0$ 到 $9$ 。

## 輸出說明:
第一行輸出共有幾個特殊位置，接下來輸 出 $k$ 行，每一行輸出兩個正整數代表作標點位。特殊位置請按照字典順序由小到 大輸出。
## 解題絲路
題目講得蠻文言文的，我自己會這樣表述:
> 對於每個位置 (i, j)，令 x = a[i][j]。
> 計算所有與 (i, j) 曼哈頓距離<= x 的點的值總和 S。
> 若 S % 10 == x，則 (i, j) 為特殊位置。

透過迴圈去**模擬**每個元素的曼哈頓距離

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int a[55][55];
vector<pair<int,int>> fans;
int main() {
    io;

    int n,m;
    cin >> n >> m;
    for (int i=0;i<n;++i)for (int j=0;j<m;++j)cin >> a[i][j];

    int ans=0;
    
    for (int i=0;i<n;++i){
        for (int j=0;j<m;++j){
            
            int x =a[i][j];
            int cnt=0;
            
            for (int q=0;q<n;q++){
                for (int p=0;p<m;p++){
                    if (abs(q-i)+abs(p-j)<=x) cnt += a[q][p];;
                }
            }
            if (cnt%10 == x){
                ans++;
                fans.push_back({i, j});
            }
        }
    }
    cout << ans << "\n";
    for (auto [x, y] : fans) cout << x << " " << y << "\n";

}

---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!
**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改 編作品必須在相同條款下分享。