http://acm.pku.edu.cn/JudgeOnline/problem?id=1231
#include <iostream> #include <cmath> #include <string> #include <algorithm> #include <iomanip> #define inf 1000005 using namespace std; struct node { int leftx; int lefty; int rightx; int righty; }arry[30]; int k; int cmp1(const void *a,const void *b) { return (*(node *)a).leftx - (*(node *)b).leftx; } int cmp2(const void *a,const void *b) { return (*(node *)a).lefty - (*(node *)b).righty; } bool check1() { qsort(arry,k,sizeof(arry[0]),cmp1); //for(int i=0;i<k;++i) //{ // cout<<arry[i].leftx<<" "<<arry[i].rightx<<endl; //} bool flag=false; for(int i=0;i<k-1;++i) { if(arry[i+1].leftx<=arry[i].rightx) { flag=true; } } if(flag) return false; else return true; } bool check2() { qsort(arry,k,sizeof(arry[0]),cmp2); bool flag = false; for(int i=0;i<k-1;++i) { if(arry[i+1].lefty <= arry[i].righty) { flag = true; } } if(flag) return false; else return true; } void solve() { bool t=check1(); if(t) { printf("YES\n"); } else { bool t1=check2(); if(t1) { printf("YES\n"); } else { bool flag =true; qsort(arry,k,sizeof(arry[0]),cmp1); for(int i=0;i<k;++i) { for(int j=i+1;j<k;++j) { if(arry[j].leftx>arry[i].rightx||arry [j].righty<arry[i].lefty||arry[j].lefty<arry[i].righty) continue; else { flag=false; break; } } } if(flag) { bool sybol1=false; bool sybol2=false; for(int i=0;i<k;++i) { sybol1=false; sybol2=false; for(int j=0;j<k;++j) { if(j!=i) { if(arry[j].rightx>=arry [i].rightx&&arry[j].leftx<=arry[i].rightx) { sybol1=true; } if((arry[j].leftx<=arry [i].leftx)&&(arry[j].rightx>=arry[i].leftx)) { sybol2=true; } } } if(sybol1&&sybol2) { flag = false; break; } } for(int i=0;i<k;++i) { sybol1=false; sybol2=false; for(int j=0;j<k;++j) { if(j!=i) { if(arry[j].righty>=arry [i].righty&&arry[j].lefty<=arry[i].righty) { sybol1=true; } if(arry[j].lefty<=arry [i].lefty&&arry[j].righty>=arry[i].lefty) { sybol2=true; } } } if(sybol1&&sybol2) { flag = false; break; } } if(flag) { //cout<<"YES"<<endl; printf("YES\n"); } else { //cout<<"NO"<<endl; printf("NO\n"); } } else { //cout<<"NO"<<endl; printf("NO\n"); } } } } void input() { int test; //cin>>test; scanf("%d",&test); int p; while(test--) { //cin>>k>>p; scanf("%d%d",&k,&p); int x,y; int minx=inf,miny=inf,maxx=0,maxy=0; for(int i=0;i<k;++i) { minx=inf; miny=inf; maxx=0; maxy=0; for(int j=0;j<p;++j) { //cin>>x>>y; scanf("%d%d",&x,&y); if(minx>x) minx=x; if(miny>y) miny=y; if(maxx<x) maxx=x; if(maxy<y) maxy=y; } arry[i].leftx=minx; arry[i].lefty=miny; arry[i].rightx=maxx; arry[i].righty=maxy; /* cout<<arry[i].leftx<<" "<<arry[i].lefty<<" "<<arry[i].rightx<<" "<<arry[i].righty<<endl;*/ } if(p==1) { printf("YES\n"); } else solve(); } } int main() { input(); return 0; }