Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

164K 0ms 1A

Posted by KatrineYang at 2016-08-30 03:00:23 on Problem 1231
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator