ZeroJudge 解題筆記：i378. 垂直對稱 (Symmetry)

作者：王一哲
日期：2025年4月11日



ZeroJudge 題目連結：i378. 垂直對稱 (Symmetry)

解題想法

相同的 x 座標上如果有奇數個點，則 y 座標正中央的點必須在水平對稱線上，而且只能有 1 個值。接著再檢查一次，相同的 x 座標上所有的點 y 座標和，必須等於水平對稱線的 y 座標乘以點的數量。

Python 程式碼

使用時間約為 32 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 個點
    ps = dict()  # x 座標: [y1, y2, ...]
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())
        if x not in ps: ps[x] = [y]
        else: ps[x].append(y)
    cand = 10000  # 水平對稱線可能的 y 座標，預設為超出題目範圍的值
    found = True  # 是否有解
    for _, ys in ps.items():  # 找相同的 x 座標中所有點的 y 座標
        ys.sort()  # 要排序
        if len(ys)%2 == 1:  # 如果有奇數個點的項目
            if cand == 10000: cand = ys[len(ys)//2]  # 如果 cand 是預設值，更新
            elif cand != ys[len(ys)//2]:  # 不相同
                found = False; break  # 無解
    if found:  # 如果只有一個 cand
        for _, ys in ps.items():  # 找相同的 x 座標中所有點的 y 座標
            if cand*len(ys) != sum(ys):  # 如果不相等，cand 不在這些點的正中央
                found = False; break  # 無解
    print("success" if found else "failure")

C++ 程式碼

這個寫法很不像 C++，完全就是 Python 的風格。使用時間約為 3 ms，記憶體約為 412 kB，通過測試。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 個點
    while(cin >> n) {
        unordered_map<int, vector<int>> ps;  // x 座標: [y1, y2, ...]
        for(int i=0; i<n; i++) {  // 讀取 n 個點
            int x, y; cin >> x >> y;
            ps[x].push_back(y);
        }
        int cand = 10000;  // 水平對稱線可能的 y 座標，預設為超出題目範圍的值
        bool found = true;  // 是否有解
        for(auto it : ps) {  // 找相同的 x 座標中所有點的 y 座標
            vector<int> ys = it.second;
            sort(ys.begin(), ys.end());  // 要排序
            if (ys.size()%2 == 1) {  // 如果有奇數個點的項目
                if (cand == 10000) cand = ys[ys.size()/2];  // 如果 cand 是預設值，更新
                else if (cand != ys[ys.size()/2]) {  // 不相同
                    found = false; break;  // 無解
                }
            }
        }
        if (found) {  // 如果只有一個 cand
            for(auto it : ps) {  // 找相同的 x 座標中所有點的 y 座標
                vector<int> ys = it.second;
                if (cand*(int)ys.size() != accumulate(ys.begin(), ys.end(), 0)) {  // 如果不相等，cand 不在這些點的正中央
                    found = false; break;  // 無解
                }
            }
        }
        cout << (found ? "success\n" : "failure\n");
    }
    return 0;
}