| ||||||||||
| 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