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 gao at 2006-07-25 21:57:43 on Problem 1899
#include <iostream.h>
#include <math.h>

class rectangle{
public:
	int x1,y1;
	int x2,y2;

	int area(){  return (x2-x1)*(y2-y1);};

	bool touch(rectangle &);
    void combine(rectangle &);

};


bool rectangle::touch(rectangle &m)
{
    if(abs(x1+x2-m.x1-m.x2)>(x2-x1+m.x2-m.x1))
		return false;
    if(abs(y1+y2-m.y1-m.y2)>(y2-y1+m.y2-m.y1))
		return false;
	return true;
}

void rectangle::combine(rectangle &m)
{
	x1=m.x1<x1?m.x1:x1;
	y1=m.y1<y1?m.y1:y1;
	x2=m.x2>x2?m.x2:x2;
	y2=m.y2>y2?m.y2:y2;
}


rectangle  A[102];
int Num=0;

void solve(rectangle temp)
{
	int i,j;

	for(i=0;i<Num;i++){
		if(temp.touch(A[i])){
			 temp.combine(A[i]);

		     for(j=i;j<Num-1;j++)
				 A[j+1]=A[j];
			 Num--;

			 solve(temp);
			 return;
		}
	}

	A[Num]=temp;
	Num++;
}


void main()
{
	long i,x,y,n,sum=0;
	rectangle temp;
	int rx,ry,r;

	cin>>x>>y>>n;

	if(n==0){
		cout<<x*y;
		return;
	}

	for(i=0;i<n;i++){
		cin>>rx>>ry>>r;
		temp.x1=rx-r;
		temp.y1=ry-r;
		temp.x2=rx+r;
		temp.y2=ry+r;
	    solve(temp);
	}

	for(i=0;i<Num;i++)
		sum+=A[i].area();
	cout<<x*y-sum;
}

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