扫描线+线段树 求矩形面积并
2 10 10 20 20 15 15 25 25.5 0
Test case #1 Total explored area: 180.00
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=11000;
int flag[maxn*10]; double sum[maxn*10];
double X[maxn];
struct Line
{
double xl,xr,y;
int s;
bool operator<(const Line &M) const
{
return y<M.y;
}
}line[maxn];
void push_up(int l,int r,int rt)
{
if(flag[rt]) sum[rt]=X[r+1]-X[l];
else if(l==r) sum[rt]=0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,int rt,int L,int R,int c)
{
if(L<=l&&r<=R)
{
flag[rt]+=c;
push_up(l,r,rt);
return ;
}
int m=(l+r)>>1;
if(R<=m) update(lson,L,R,c);
else if(L>m) update(rson,L,R,c);
else
{
update(lson,L,m,c);
update(rson,m+1,R,c);
}
push_up(l,r,rt);
}
int find(double x,int k)
{
int low=1,high=k,mid;
while(low<=high)
{
mid=(low+high)/2;
if(X[mid]==x) return mid;
else if(X[mid]>x) high=mid-1;
else low=mid+1;
}
}
int main()
{
int n,cas=1;
while(scanf("%d",&n)!=EOF&&n)
{
memset(flag,0,sizeof(flag));
memset(sum,0,sizeof(sum));
int num=0;
for(int i=0;i<n;i++)
{
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[++num]=(Line){x1,x2,y1,1};
X[num]=x1;
line[++num]=(Line){x1,x2,y2,-1};
X[num]=x2;
}
sort(X+1,X+1+num);
sort(line+1,line+1+num);
int k=1;
for(int i=2;i<=num;i++)
{
if(X[i]!=X[i-1]) X[++k]=X[i];
}
double ans=0;
for(int i=1;i<num;i++)
{
int l=find(line[i].xl,k);
int r=find(line[i].xr,k)-1;
update(1,k,1,l,r,line[i].s);
ans+=sum[1]*(line[i+1].y-line[i].y);
}
printf("Test case #%d\n",cas++);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}
原文:http://blog.csdn.net/u012797220/article/details/18793429