說實話 真是水題 題目給的數據太小 都不用離散化 之前用離散化處理一個類似的題
這道題是給你幾個矩形 讓你求覆蓋面積 重復的只算一次
做完之後被坑了 題目說輸入左下角和右下角坐標 但是 左上角和右下角也有可能 只要是對角就行 所有得線處理一下
#include
#include
#include
#include
using namespace std;
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)
struct node
{
int y,x1,x2;
int flash;
}A[2*5000];
int num[110*4];
int Min(int a,int b)
{
return a
int Max(int a,int b)
{
return a>b?a:b;
}
int cmp(node a,node b)
{
return a.y
int update(int L,int R,int left,int right,int mark,int k)
{
int mid=(L+R)/2;
if(L==left&&right==R)
{
if(num[mark]>=0)
{
num[mark]+=k;
}
else
{
update(L,mid,L,mid,LL(mark),k);
update(mid,R,mid,R,RR(mark),k);
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
}
}
else
{
if(num[mark]>=0)
{
num[LL(mark)]=num[mark];
num[RR(mark)]=num[mark];
}
if(right<=mid)
{
update(L,mid,left,right,LL(mark),k);
}
else if(left>=mid)
{
update(mid,R,left,right,RR(mark),k);
}
else
{
update(L,mid,left,mid,LL(mark),k);
update(mid,R,mid,right,RR(mark),k);
}
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
else num[mark]=-1;
}
return 0;
}
int find(int L,int R,int mark)
{
int dis=0;
int mid=(L+R)/2;
if(num[mark]==0) return 0;
if(num[mark]>0)
{
dis+=R-L;
return dis;
}
dis+=find(L,mid,LL(mark))+find(mid,R,RR(mark));
return dis;
}
int main()
{
int x1,y1,x2,y2;
int i,j;
while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2))
{
if(x1==-2) break;
i=1;
while(1)
{
A[i].y=Min(y1,y2);
A[i].x1=A[i+1].x1=Min(x1,x2);
A[i].x2=A[i+1].x2=Max(x1,x2);
A[i+1].y=Max(y1,y2);
A[i].flash=1;
A[i+1].flash=-1;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1<0) break;
i+=2;
}
i++;
sort(A+1,A+1+i,cmp);
memset(num,0,sizeof(num));
int area=0,a,b;
a=A[1].x1;
b=A[1].x2;
update(0,100,a,b,1,1);
for(int j=2;j<=i;j++)
{ //printf("^^^^\n");
a=A[j].x1;
b=A[j].x2;
area+=(A[j].y-A[j-1].y)*find(0,100,1);
if(A[j].flash==1)
{
update(0,100,a,b,1,1);
}
else
{
update(0,100,a,b,1,-1);
}
}
printf("%d\n",area);
if(x1==-2) break;
}
return 0;
}
