d555

輸入說明 ：

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

輸出說明 ：

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

先定義一個結構,代表一個點,然後把輸入讀進結構陣列裡面,排序這個陣列,順序是x從大到小,x一樣的話y大的放前面

排序完的第1個點,一定是Dominate point,因為它一定x最大,y也最大

再來找它左邊比它高個點,找到之後,再找比第2個Dominate point左邊,且比它高的點

依序找完整個陣列

#include<stdio.h>
#include<stdlib.h>
struct Point
{
    int x;
    int y;    
};

int cmp(const void * pa,const void *pb)
{
    Point *p1 =(Point *)pa; 
    Point *p2 =(Point *)pb;

    if(p1->x != p2->x)
        return p1->x < p2->x;
    else
        return p1->y < p2->y;
}

int cmpans(const void * pa,const void *pb)
{
    Point *p1 =(Point *)pa; 
    Point *p2 =(Point *)pb;

    return p1->x > p2->x;
}

Point a[500000];

int main()
{
    int N;
    int times=0;

    while(scanf("%d",&N)!=EOF)
    {
        int tempN = N;
        int i=0;
        times++;

        while(tempN--)   
        {
            scanf("%d %d",&a[i].x,&a[i].y);
            i++;
        }

        qsort(a,N,sizeof(Point),cmp);   //先比x在比y大的在前面 

        Point ans[50000];
        int count=1;

        ans[0]=a[0]; 
        int x = a[0].x;
        int y = a[0].y;

        for(i=1;i<N;i++)
        {
            if(a[i].x==x) continue;

            if(a[i].y>y)
            {
                y=a[i].y;
                ans[count]=a[i];
                count++;
            }
        }

        qsort(ans,count,sizeof(Point),cmpans);

        //輸出

        printf("Case %d:\n",times);
        printf("Dominate Point: %d\n",count);

        for(i=0;i<count;i++)
        {
            printf("(%d,%d)\n",ans[i].x,ans[i].y);

        }
    }
    return 0;
}