题解 | #最大点集#

#include #include<math.h> using namespace std; int main() { long int a[500000][2]={0}; long int b[500000][2]={0}; long int mark[500000]={0}; long int N,loop,loops,loopx,loopy; bool Key=true; cin>>N; for(loop=0;loop<N;loop++) { cin>>a[loop][0]; cin>>a[loop][1]; }

for(loop=0;loop<N;loop++)
{
    for(loops=0;loops<N ;loops++)
    {
        if(a[loops][0]>a[loop][0] and a[loops][1]>a[loop][1])
        {
            mark[loop]=1;
            //cout<<loop<<loops<<endl;
            break;
        }
            
    }
}
int num=0;
for(loop=0;loop<N;loop++)
{
    if (mark[loop]<1)
    {
        b[num][0]=a[loop][0];
        b[num][1]=a[loop][1];
        num=num+1;
        //cout<<a[loop][0]<<' '<<a[loop][1]<<endl;
    }
}
while(Key)
{
    Key=false;
    for(loop=0;loop<num-1;loop++)
    {
        if(b[loop][0]>b[loop+1][0])
        {
            loopx=b[loop][0];
            loopy=b[loop][1];
            b[loop][0]=b[loop+1][0];
            b[loop][1]=b[loop+1][1];
            b[loop+1][0]=loopx;
            b[loop+1][1]=loopy;
            Key=true;
        }
    }
}
for(loop=0;loop<num;loop++)
{
    
    cout<<b[loop][0]<<' '<<b[loop][1]<<endl;
    
}

}