Counting Squares[HDU1264]
2844 ワード
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 DescriptionYour 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 line5 8 7 10specifies 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.
InputThe 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.
OutputYour output should be the number of squares covered by each set of rectangles. Each number should be printed on a separate line.
Sample Input5 8 7 106 9 7 86 8 8 11-1 -1 -1 -10 0 100 10050 75 12 9039 42 57 73-2 -2 -2 -2
Sample Output810000
Source浙江工業大学第4回大学生プログラム設計コンテスト
RecommendJGShining
浮遊法の簡単な応用
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1072 Accepted Submission(s): 529
Problem DescriptionYour 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 line5 8 7 10specifies 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.
InputThe 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.
OutputYour output should be the number of squares covered by each set of rectangles. Each number should be printed on a separate line.
Sample Input5 8 7 106 9 7 86 8 8 11-1 -1 -1 -10 0 100 10050 75 12 9039 42 57 73-2 -2 -2 -2
Sample Output810000
Source浙江工業大学第4回大学生プログラム設計コンテスト
RecommendJGShining
浮遊法の簡単な応用
#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
",ans);
if (xx1==-2) return 0;
}
return 0;
}