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

哪位大哥提供一点测试数据,从昨天检查到现在,实在不知道哪里错了,跪谢了!!!

Posted by zskof at 2004-10-11 14:00:11 on Problem 1899
#include <stdio.h>
#include <math.h>

typedef struct rectangle{
	int x1,y1;
	int x2,y2;
	struct rectangle *next;
}RECT;

bool contain(RECT o,RECT n){
	if(o.x1<=n.x1&&o.x2>n.x1
		&&o.x1<n.x2&&o.x2>=n.x2
		&&o.y1<=n.y1&&o.y2>n.y1
		&&o.y1<n.y2&&o.y2>=n.y2)
	{
		return true;
	}
	else
		return false;
}

bool intersect(RECT o,RECT n){
	if(o.x1<=n.x2&&o.x2>=n.x1&&o.y1<=n.y2&&o.y2>=n.y1)
		return true;
	else
		return false;
}
void combine(RECT o,RECT &n){
	n.x1=o.x1>n.x1?n.x1:o.x1;
	n.y1=o.y1>n.y1?n.y1:o.y1;
	n.x2=o.x2>n.x2?o.x2:n.x2;
	n.y2=o.y2>n.y2?o.y2:n.y2;
}
void procedure(int x,int y,int n){
	RECT temp,*head=NULL,*tail,*p,*t;
	int rx,ry,r;
	int i,sum,result;
	bool skip;
	if(n==0){
		printf("%d\n",x*y);
		return;
	}
	for(i=0;i<n;i++){
		scanf("%d %d %d",&rx,&ry,&r);
		temp.x1=rx-r;
		temp.y1=ry-r;
		temp.x2=rx+r;
		temp.y2=ry+r;
		skip=false;
		while(1){
			for(p=head;p;p=p->next){
				if(contain(*p,temp)){
					skip=true;
					p=NULL;
					break;
				}
				if(intersect(*p,temp)){
					combine(*p,temp);
					if(p==head){
						head=head->next;
					}
					else{
						for(t=head;t->next!=p;t=t->next);
						t->next=p->next;
					}
					break;
				}
			}
			if(p==NULL)
				break;
		}
		if(!skip){
			p=new RECT;
			p->x1=temp.x1;
			p->x2=temp.x2;
			p->y1=temp.y1;
			p->y2=temp.y2;
			if(head==NULL){
				head=p;
				tail=p;
				head->next=NULL;
			}
			else{
				tail->next=p;
				tail=p;
				tail->next=NULL;
			}
		}
	}
	for(p=head,sum=0;p;p=p->next)
		sum+=(p->x2-p->x1)*(p->y2-p->y1);
	result=x*y-sum;
	printf("%d\n",result);
}
int main(){
	int x,y,n;
	scanf("%d %d",&x,&y);
	scanf("%d",&n);
	procedure(x,y,n);
}

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