poj1389:http://poj.org/problem?id=1389
题意:求矩形面积的并
题解:扫描线加线段树 同poj1389
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int num;
struct Node{
int l;
int r;
int tp;
int y;
bool operator <(Node a) const{
return y<a.y;
}
}line[*maxn];
int arr[*maxn];
struct Edge{
int left;
int right;
int flag;
int sum;
}node1[maxn*];
void build(int l,int r,int idx){
node1[idx].left=l;
node1[idx].right=r;
if(l==r){
node1[idx].flag=;
node1[idx].sum=;
return;
}
int mid=(l+r)/;
build(l,mid,idx<<);
build(mid+,r,idx<<|);
node1[idx].sum=node1[idx<<].sum+node1[idx<<|].sum;
}
void update(int l,int r,int f,int idx){
if(node1[idx].left==node1[idx].right){
node1[idx].flag+=f;
if(node1[idx].flag)node1[idx].sum=arr[node1[idx].right+]-arr[node1[idx].left];
if(!node1[idx].flag)node1[idx].sum=;
return ;
}
int mid=(node1[idx].left+node1[idx].right)/;
if(mid>=r)update(l,r,f,idx<<);
else if(mid<l)update(l,r,f,idx<<|);
else{
update(l,mid,f,idx<<);
update(mid+,r,f,idx<<|);
}
node1[idx].sum=node1[idx<<].sum+node1[idx<<|].sum;
}
int binaryserach(int x){
int l,r,mid;
l=,r=num+;
while (r-l>){
mid=(l+r)>>;
if (arr[mid]<=x) l=mid;
else r=mid;
}
return l;
}
int main(){
int n;int x1,y1,x2,y2;
long long ans;
while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
if(x1==-&&x2==-&&y1==-&&y2==-)break;
num=;int cnt=;
line[].l=x1;line[].r=x2;line[].y=y1;line[].tp=;
line[].l=x1;line[].r=x2;line[].y=y2;line[].tp=-;
arr[++num]=x1;arr[++num]=x2;
while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
if(x1==-&&x2==-&&y1==-&&y2==-)break; line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=y1;line[cnt].tp=;
line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=y2;line[cnt].tp=-;
arr[++num]=x1;arr[++num]=x2;
} sort(arr+,arr+num+);
ans=;
sort(line+,line+cnt+);
build(,cnt,);
for(int i=;i<=cnt;i++){
ans+=node1[].sum*(line[i].y-line[i-].y);
int l=binaryserach(line[i].l);
int r=binaryserach(line[i].r)-;
update(l,r,line[i].tp,);
} printf("%I64d\n",ans);
}
}