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

在搜索之前先对矩形进行排序,不过WA了,实在想不到错在哪里,望指教!

Posted by piaolingqingsi at 2008-04-01 09:16:19 on Problem 1468 and last updated at 2008-04-03 13:52:18
/*
 *      pku1468.cpp
 *      
 */


#include <iostream>

struct rect{
	int x1,x2,y1,y2;
}r[5001];

int cmp(const void* a, const void* b){
	return (*(rect *)b).x1-(*(rect *)a).x1 ||   // b.x1 > a.x1
		     ( ((*(rect *)b).x1==(*(rect *)a).x1) &&((*(rect *)a).x2-(*(rect *)b).x2) ) ||  // b.x1 = a.x1而b.x2 < a.x2
		    ((*(rect *)b).x1==(*(rect *)a).x1) &&((*(rect *)a).x2==(*(rect *)b).x2) &&((*(rect *)b).y1-(*(rect *)a).y1) ||  // b.x1 = a.x1, b.x2 = a.x2,  b.y1 > a.y1
		   ((*(rect *)b).x1==(*(rect *)a).x1) &&((*(rect *)a).x2==(*(rect *)b).x2) &&((*(rect *)b).y1==(*(rect *)a).y1) && ((*(rect *)a).y2-(*(rect *)b).y2)  ;	// b.x1 = a.x1, b.x2 = a.x2,  b.y1 = a.y1 , b.y2<a.y2;
}

bool cover(int a, int b) //如 a cover b,return true;
{
	return (r[a].x1<=r[b].x1 && r[a].x2>=r[b].x2 && r[a].y1<=r[b].y1 &&r[a].y2>=r[b].y2) ;
}

int main(void)
{
//	freopen("in.txt","r",stdin);
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j;
		int result=0;
		for(i=0;i<n;++i)
		scanf("%d%d%d%d",&r[i].x1, &r[i].x2, &r[i].y1, &r[i].y2 );
		qsort(r,n,sizeof(rect),(int(*)(const void*, const void*))cmp); //所有的矩形排序。
//	    for(i=0; i<n;++i)
 // 	printf("%d %d %d %d\n",r[i].x1, r[i].x2, r[i].y1, r[i].y2);
		for(i=0;i<n; ++i){
			if(i!=0 && cover(i-1,i)){   //当矩形i-1和矩形i全等的时候,互为覆盖,结果+1
				result++;
				continue;
		}
			for(j=i+1;j<n;++j){
				if(cover(j,i)){  //如 j cover i,return true;
					result++;
					break;
				}
			}
		}
		printf("%d\n",result);
	}
	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