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;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
