Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
164K 0ms 1A#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; struct zimu{ int xmin, xmax, ymin, ymax; }zms[30], zms_[30]; bool compare(const zimu& z1, const zimu &z2){ return z1.xmin < z2.xmin || (z1.xmin == z2.xmin && z1.ymin < z2.ymin); } bool compare_(const zimu& z1, const zimu &z2){ return z1.ymin < z2.ymin || (z1.ymin == z2.ymin && z1.ymin < z2.ymin); } bool noItsc(int start1, int end1, int start2, int end2){ return start1 > end2 || start2 > end1; } int mx(int a, int b){ return (a>b)? a : b; } int main() { int T; scanf("%d", &T); for(int ii = 0; ii < T; ii++){ int K, P; scanf("%d%d", &K, &P); for(int i = 0; i < K; i++){ zms[i].xmin = 2147483647, zms[i].xmax = -1, zms[i].ymin = 2147483647, zms[i].ymax = -1; for(int j = 0; j < P; j++){ int x, y; scanf("%d%d", &x, &y); if(x < zms[i].xmin) zms[i].xmin = x; if(x > zms[i].xmax) zms[i].xmax = x; if(y < zms[i].ymin) zms[i].ymin = y; if(y > zms[i].ymax) zms[i].ymax = y; } zms_[i].xmin = zms[i].xmin, zms_[i].xmax = zms[i].xmax; zms_[i].ymin = zms[i].ymin, zms_[i].ymax = zms[i].ymax; } if(K == 1){ printf("YES\n"); continue; } sort(zms, zms+K, compare); sort(zms_, zms_+K, compare_); bool bxj = 1; for(int i = 0; i < K-1; i++){ for(int j = i+1; j < K; j++){ if(!noItsc(zms[i].xmin, zms[i].xmax, zms[j].xmin, zms[j].xmax) && !noItsc(zms[i].ymin, zms[i].ymax, zms[j].ymin, zms[j].ymax)){ bxj = 0; break; } } } if(!bxj){ printf("NO\n"); continue; } int start = zms[0].xmin, end = zms[0].xmax; int startArg = 0, endArg = 0; int cur = 1; while(cur < K){ if(zms[cur].xmin <= end){ end = mx(end, zms[cur].xmax); for(int k = cur-1; k >= startArg; k--){ if(!noItsc(zms[k].ymin, zms[k].ymax, zms[cur].ymin, zms[cur].ymax)){ bxj = 0; break; } } if(!bxj) break; endArg ++; } else{ start = zms[cur].xmin, end = zms[cur].xmax; startArg = cur, endArg = cur; } cur++; } if(!bxj){ printf("NO\n"); continue; } start = zms_[0].ymin, end = zms_[0].ymax; startArg = 0, endArg = 0; cur = 1; while(cur < K){ if(zms_[cur].ymin <= end){ end = mx(end, zms_[cur].ymax); for(int k = cur-1; k >= startArg; k--){ if(!noItsc(zms_[k].xmin, zms_[k].xmax, zms_[cur].xmin, zms_[cur].xmax)){ bxj = 0; break; } } if(!bxj) break; endArg ++; } else{ start = zms_[cur].ymin, end = zms_[cur].ymax; startArg = cur, endArg = cur; } cur++; } if(!bxj){ printf("NO\n"); continue; } printf("YES\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator