题解 P2772 【寻找平面上的极大点】

shiningrise · 2018-01-06 19:02:24 · 题解

在纸上把测试数据一画，就知道

贪心 先按y排序，y相同按x排序

第一点肯定就是极大点了，因为没有点y比他大

接下来就把这个极大点的x记下，之后第一个出现x比前一个极大点x大的点就是极大点

    #include<bits/stdc++.h>
    using namespace std;
    struct Node {
        int x;int y;
        bool operator <(const Node &b)const
        {
            if(y==b.y)return x>b.x; 
            return y>b.y;
        }
    }a[500005];
    int main()
    {
         std::ios::sync_with_stdio(false);
        int n;
        cin>>n; 
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        sort(a,a+n);
        int f=1;
        int last =-1;
        for(int i=0;i<n;i++)
        {
            if(a[i].x>last)
            {
                last = a[i].x;
                if(f)f=0;else cout<<",";
                cout<<"("<<a[i].x<<","<<a[i].y<<")";
            }
        }
        return 0;
    }