d555: 平面上的極大點

2019-08-31

內容 d555: 平面上的極

在平面上如果有兩個點 ( x , y ) 與 ( a , b ),我們說 ( x , y ) 支配(Dominate)了

( a , b )這就是指 x ≧ a 而且 y ≧ b；用圖來看就是 ( a , b ) 座落在以 ( x , y ) 為右上角的
一點無的區域中。

對於平面上的任意一個有限點集合而言，一定存在有若干個點，它們不會被

集合中的內一點所支配，這些個數就構成一個所謂的極大集合。請寫一個程式，
讀入一個新的集合，找出這個集合中的極大值。

※簡單的說若找不到一點在 ( x , y ) 的右上方,則 ( x , y ) 就要輸出

輸入

每個測資的第一行有一個數字 N ( 1 ≦ N ≦ 50,0000 )，代表接下來有 N 行，
每行上有兩個數字 x , y ( 0 ≦ X,Y ≦ 100000 )
分別代表一點的 X 軸座標，與 Y 軸座標。

11
0 8
1 10
3 4
4 6
4 9
5 8
6 9
7 5
8 7
9 8
10 6

輸出

請依照 X 軸的大小,由小輸出至大,剩餘的請參考 Sample Out。

Case 1:
Dominate Point: 4
(1,10)
(6,9)
(9,8)
(10,6)

提示

解題思路

最極端的點 (x 或 y 最大的點) 必為支配點，因為沒有其他點比他的 x(或 y)大。
如果要判斷 a 點是否支配於 b 點，只要判斷 a 點的 x 和 y 是否皆小於 b 點即可。

所以藉由第一個規則，就可以先找出第一個支配點，再用第二個規則找出不被已知支配點支配的新支配點，如此循環找査直到所有點都被判斷過即可。

Ex:

x 最大 (暫稱他為第一支配點)
x 比第一支配點的 x 還小，但 y 比第一支配點的 y 大 (暫稱他為第二支配點)
x 比第二支配點的 x 還小，但 y 比第二支配點的 y 大 (暫稱他為第三支配點)
x 比第三支配點的 x 還小，但 y 比第三支配點的 y 大
…

而由於已知第一支配點的 x 為本組數列之最大值，故判斷時只需要判斷 y 即可。

完整程式碼

AC (0.2s, 7.7MB)

#include <stdio.h>
#include <stdlib.h>
#define MAX 500000

typedef struct Point
{
    int x, y;
} Point;

Point list[MAX];

int cmp(const Point* lhs, const  Point* rhs)
{
    return (*rhs).x != (*lhs).x ? (*rhs).x - (*lhs).x : (*rhs).y - (*lhs).y;
}

int main()
{
    int n, len, yMax;
    for (int kase = 1; scanf(" %d", &n) == 1; kase++)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d %d", &list[i].x, &list[i].y);
        qsort(list, n, sizeof(Point), cmp);
        yMax = list[0].y, len = 1;
        for (int i = 1; i < n; i++)
        {
            if (list[i].y > yMax)
            {
                list[len++] = list[i];
                yMax = list[i].y;
            }
        }
        printf("Case %d:\nDominate Point: %d\n", kase, len);
        for (int i = len - 1; ~i; i--)
            printf("(%d,%d)\n", list[i].x, list[i].y);
    }
    return 0;
}