ZeroJudge 解題筆記：b604. Center of Symmetry

作者：王一哲
日期：2025年7月31日


ZeroJudge 題目連結：b604. Center of Symmetry

解題想法

比較直接的作法，先將所有的點座標 (x, y) 存入集合之中，同時計算所有點座標的平均值 (xc, yc)。接下來從集合中取出一個點，計算對稱點的座標 (xn, yn)，檢查 (xn, yn) 是否在集合之中，如果沒有就可以印出 no 並停止檢查，反之從集合中移除 (xn, yn)，重複這個過程直到集合清空為止。如果集合可以清空，印出 yes。
另一個作法，是將所有的點存入陣列、由小到大排序。因為排在陣列最前面的點，其對稱點一定在陣列的最後面。由陣列兩端向中間檢查，只要頭尾兩個點不對稱，就可以印出 no 並停止檢查。如果可以檢查完整個陣列，印出 yes。

Python 程式碼

寫法1，從集合 points 中取出點，找到對稱點並移除。使用時間約為 0.1 s，記憶體約為 5.8 MB，通過測試。

def solve(n):
    points = set()  # 儲存點 (x, y) 的集合
    xc, yc = 0, 0  # 中心點座標 (xc, yc)
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())  # 讀取點座標 (x, y)
        x *= 2; y *= 2  # 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y  # 先計算加總
        points.add((x, y))  # 將 (x, y) 加入 points
    ### end of for loop ###
    xc //= n; yc //= n  # 除以 n，取平均
    while points:  # 如果 points 還有資料繼續執行
        x, y = points.pop()  # 從 points 隨機取出一筆資料
        xn, yn = 2*xc - x, 2*yc - y  # 計算對稱點座標 (xn, yn)
        if (xn, yn) not in points:  # 如果 (xn, yn) 不在 points 之中
            return False  # 回傳 False
        points.remove((xn, yn))  # 否則從 points 中移除 (xn, yn)
    ### end of while loop ###
    return True  # 跑到這行代表有解，回傳 True

while True:
    n = int(input())  # 讀取點數 n
    if n == 0: break  # 如果讀到 0 中止迴圈
    print("yes" if solve(n) else "no")

寫法2，將點依照 x、y 由小到大排序，使用時間約為 93 ms，記憶體約為 5.5 MB，通過測試。

def solve(n):
    points = []  # 儲存點 (x, y) 的串列
    xc, yc = 0, 0  # 中心點座標 (xc, yc)
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())  # 讀取點座標 (x, y)
        x *= 2; y *= 2  # 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y  # 先計算加總
        points.append((x, y))  # 將 (x, y) 加入 points
    ### end of for loop ###
    points.sort()
    xc //= n; yc //= n  # 除以 n，取平均
    for i in range(n//2):  # 從兩端往中間檢查
        x1, y1 = points[i]
        x2, y2 = points[n-i-1]
        if x1+x2 != 2*xc or y1+y2 != 2*yc:  # 如果這兩個點的中點不是 (xc, yc)
            return False  # 回傳 False
    ### end of while loop ###
    return True  # 跑到這行代表有解，回傳 True

while True:
    n = int(input())  # 讀取點數 n
    if n == 0: break  # 如果讀到 0 中止迴圈
    print("yes" if solve(n) else "no")

C++ 程式碼

寫法1，從集合 points 中取出點，找到對稱點並移除。使用時間約為 8 ms，記憶體約為 744 kB，通過測試。

#include <cstdio>
#include <set>
#include <utility>
using namespace std;

bool solve(int n) {
    set<pair<int, int>> points;  // 儲存點 (x, y) 的集合
    int xc = 0, yc = 0;  // 中心點座標 (xc, yc)
    for(int i=0; i<n; i++) {  // 讀取 n 個點
        int x, y; scanf("%d %d", &x, &y);  // 讀取點座標 (x, y)
        x *= 2; y *= 2;  // 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y;  // 先計算加總
        points.insert(make_pair(x, y));  // 將 (x, y) 加入 points
    }
    xc /= n; yc /= n;  // 除以 n，取平均
    while(!points.empty()) {  // 如果 points 還有資料繼續執行
        auto it = points.begin();  // 取出 points 開頭的資料
        int x = (*it).first, y = (*it).second;
        points.erase(it);
        auto it2 = points.find(make_pair(2*xc - x, 2*yc - y));  // 對稱點座標是否在 points 之中
        if (it2 == points.end()) return false;  // 如果對稱點不在 points 之中回傳 alse
        points.erase(it2);  // 否則從 points 中移除對稱點
    }
    return true;  // 跑到這行代表有解，回傳 True
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        if (solve(n)) puts("yes");
        else puts("no");
    }
    return 0;
}

寫法2，將點依照 x、y 由小到大排序，使用時間約為 6 ms，記憶體約為 552 kB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

bool solve(int n) {
    vector<pair<int, int>> points;  // 儲存點 (x, y) 的陣列
    int xc = 0, yc = 0;  // 中心點座標 (xc, yc)
    for(int i=0; i<n; i++) {  // 讀取 n 個點
        int x, y; scanf("%d %d", &x, &y);  // 讀取點座標 (x, y)
        x *= 2; y *= 2;  // 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y;  // 先計算加總
        points.push_back(make_pair(x, y));  // 將 (x, y) 加入 points
    }
    sort(points.begin(), points.end());  // 排序
    xc /= n; yc /= n;  // 除以 n，取平均
    for(int i=0; i<n/2; i++) {  // 從兩端往中間檢查
        int x1 = points[i].first, y1 = points[i].second, x2 = points[n-i-1].first, y2 = points[n-i-1].second;
        if (x1+x2 != 2*xc || y1+y2 != 2*yc) return false;  // 如果這兩個點的中點不是 (xc, yc) 回傳 False
    }
    return true;  // 跑到這行代表有解，回傳 True
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        if (solve(n)) puts("yes");
        else puts("no");
    }
    return 0;
}