ZeroJudge 解題筆記：d555. 平面上的極大點

作者：王一哲
日期：2025年8月29日


ZeroJudge 題目連結：d555. 平面上的極大點

解題想法

先讀取所有點的座標存入二維串列 points，由大到小排序。用變數 max_y 記錄目前最高的 y 座標，預設值為負無窮大。從 points 之中依序讀取點的座標 x, y，如果符合以下兩種狀況，將 (x, y) 加入答案 ans 之中：

1. y 大於 max_y
2. ans 之中沒有任何一個點可以支配 (x, y)

最後將 ans 排序再印出。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    ca += 1
    print(f"Case {ca:d}:")
    n = int(line)
    point = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    print(f"Dominate Point: {len(ans):d}")
    for x, y in ans: print(f"({x:d},{y:d})")

使用時間約為 2.5 s，記憶體約為 113.2 MB，通過測試。

import sys

ca = 0
result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    ca += 1
    result.append(f"Case {ca:d}:\n")
    n = int(lines[idx])
    idx += 1
    point = sorted([tuple(map(int, line.split())) for line in lines[idx:idx+n]], reverse=True)
    idx += n
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    result.append(f"Dominate Point: {len(ans):d}\n")
    for x, y in ans: result.append(f"({x:d},{y:d})\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 27 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>  // for sort
#include <functional>  // for greater
using namespace std;

int main() {
    int ca = 0, n;
    while(scanf("%d", &n) != EOF) {
        ca++;
        printf("Case %d:\n", ca);
        vector<vector<int>> point (n, vector<int> (2));
        for(int i=0; i<n; i++) scanf("%d %d", &point[i][0], &point[i][1]);
        sort(point.begin(), point.end(), greater<vector<int>> ());
        vector<vector<int>> ans;  // 答案
        int max_y = -1000000;  // 目前最高的 y 座標，預設為極小值
        for(auto p : point) {  // 從 point 依序讀取點的座標 (x, y)
            int x = p[0], y = p[1];
            if (y > max_y) {  // y 大於 max_y
                ans.push_back({x, y});  // {x, y} 加入 ans
                max_y = y;  // 更新 max_y
            } else {  // 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
                bool state = true;  // 狀態預設為 true
                for(auto a : ans) {
                    int px = a[0], py = a[1];
                    if (px >= x && py >= y) {
                        state = false;
                        break;
                    }
                }
                if (state) ans.push_back({x, y});
            }
        }
        sort(ans.begin(), ans.end());  // 由小到大排序
        printf("Dominate Point: %lu\n", ans.size());
        for(auto a : ans) printf("(%d,%d)\n", a[0], a[1]);
    }
    return 0;
}