Counting Squares

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1072????Accepted Submission(s): 529

?

Problem Description
Your input is a series of rectangles, one per line. Each rectangle is specified as two points(X,Y) that specify the opposite corners of a rectangle. All coordinates will be integers in the range 0 to 100. For example, the line
5 8 7 10
specifies the rectangle who's corners are(5,8),(7,8),(7,10),(5,10).
If drawn on graph paper, that rectangle would cover four squares. Your job is to count the number of unit(i.e.,1*1) squares that are covered by any one of the rectangles given as input. Any square covered by more than one rectangle should only be counted once.

?

?

?

Input
The input format is a series of lines, each containing 4 integers. Four -1's are used to separate problems, and four -2's are used to end the last problem. Otherwise, the numbers are the x-ycoordinates of two points that are opposite corners of a rectangle.

?

?

?

Output
Your output should be the number of squares covered by each set of rectangles. Each number should be printed on a separate line.

?

?

?

Sample Input
5 8 7 10
6 9 7 8
6 8 8 11
-1 -1 -1 -1
0 0 100 100
50 75 12 90
39 42 57 73
-2 -2 -2 -2
?

?

Sample Output
8
10000
?

?

Source
浙江工業大學第四屆大學生程序設計競賽
?

?

Recommend
JGShining

漂浮法的簡單應用

      #include<stdio.h>

int l[5000],r[5000],u[5000],d[5000],N,ans;

void dfs(int ll,int rr,int uu,int dd,int dep)

{

	if (dep==N)

	{

		ans+=(rr-ll)*(uu-dd);

		return;

	}

	if (ll==rr || uu==dd) return;

	if (rr<=l[dep+1] || r[dep+1]<=ll || u[dep+1]<=dd || uu<=d[dep+1]) dfs(ll,rr,uu,dd,dep+1);

	else

	{

		if (ll<l[dep+1] && l[dep+1]<rr)

		{

			dfs(ll,l[dep+1],uu,dd,dep+1);

			ll=l[dep+1];

		}

		if (ll<r[dep+1] && r[dep+1]<rr)

		{

			dfs(r[dep+1],rr,uu,dd,dep+1);

			rr=r[dep+1];

		}

		if (dd<u[dep+1] && u[dep+1]<uu)

		{

			dfs(ll,rr,uu,u[dep+1],dep+1);

			uu=u[dep+1];

		}

		if (dd<d[dep+1] && d[dep+1]<uu)

		{

			dfs(ll,rr,d[dep+1],dd,dep+1);

			dd=d[dep+1];

		}

	}

}

int main()

{

	while (true)

	{

		N=0;

		int xx1,xx2,yy1,yy2,i;

		while (scanf("%d%d%d%d",&xx1,&yy1,&xx2,&yy2)!=EOF)

		{

			N++;

			if (xx1<xx2)

			{

				l[N]=xx1;

				r[N]=xx2;

			}

			else

			{

				l[N]=xx2;

				r[N]=xx1;

			}

			if (yy1<yy2)

			{

				u[N]=yy2;

				d[N]=yy1;

			}

			else

			{

				u[N]=yy1;

				d[N]=yy2;

			}

			if (xx1<0)

			{

				N--;

				break;

			}

		}

		ans=0;

		for (i=1;i<=N;i++) dfs(l[i],r[i],u[i],d[i],i);

		printf("%d\n",ans);

		if (xx1==-2) return 0;

	}

	return 0;

}


    

?

Counting Squares[HDU1264]