POJ1389 Area of Simple Polygons 线段树

POJ1389 给定n个整数点矩形，求面积并。

显然ans必然是整数。

记录若干个事件，每个矩形的左边的竖边记为开始，右边的竖边记为结束。

进行坐标离散化后用线段树维护每个竖的区间， 就可以快速积分了。

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn=100005;
struct Rectangle
{
 int x1,y1,x2,y2;	
};

struct Event
{
 int x,y1,y2,add;	
};

struct IntervalTreeNode
{
 int count,total;	
};

int n;

Rectangle rect[maxn];
Event evt[maxn<<1];
IntervalTreeNode tree[(maxn+10)<<2];
int id[maxn<<1];
bool cmp(const Event &a,const Event &b)
{
 if(a.x<b.x)return true;
 	return false;
}

void up(int i,int lb,int rb)
{
 tree[i].total=tree[i<<1].total+tree[(i<<1)+1].total;
 if(tree[i].count)tree[i].total=id[rb]-id[lb];
}

void ins(int i,int lb,int rb,int a,int b,int k)
{
 if(a==lb&&b==rb){
 	tree[i].count+=k;
 	up(i,lb,rb);
 	return ;
 }
 int med=(lb+rb)>>1;
 if(b<=med) ins(i<<1,lb,med,a,b,k);
 	else if(a>=med)ins((i<<1)+1,med,rb,a,b,k);
 		else{
 			 ins(i<<1,lb,med,a,med,k);
 			 ins((i<<1)+1,med,rb,med,b,k);
		 }
 up(i,lb,rb);
}

long long area()
{
 for(int i=0;i<n;i++){
 	id[i]=rect[i].y1;
 	id[i+n]=rect[i].y2;
 }
 sort(id,id+2*n);
 for(int i=0;i<2*n;i++){
 	rect[i].y1=lower_bound(id,id+2*n,rect[i].y1)-id;
 	rect[i].y2=lower_bound(id,id+2*n,rect[i].y2)-id;//坐标离散化 
 }
 for(int i=0;i<n;i++){
 	evt[i].add=1;
 	evt[i+n].add=-1;
 	evt[i].x=rect[i].x1;
 	evt[i+n].x=rect[i].x2;
 	evt[i].y1=evt[i+n].y1=rect[i].y1;
 	evt[i].y2=evt[i+n].y2=rect[i].y2;
 }
 sort(evt,evt+n*2,cmp);
 long long int ans=0;
 for(int i=0;i<2*n;i++){
 	if(i>0&&evt[i].x>evt[i-1].x){
 		ans+=(long long )(evt[i].x-evt[i-1].x)*tree[1].total;
	 }
	ins(1,0,2*n-1,evt[i].y1,evt[i].y2,evt[i].add);
 }
 return ans;
}

int main()
{freopen("t.txt","r",stdin);
 while(true)
 {
 	n=0;
 	scanf("%d%d%d%d",&rect[0].x1,&rect[0].y1,&rect[0].x2,&rect[0].y2);
 	if(rect[0].x1==-1)return -1;
 	while(++n)
 		{
 		 scanf("%d%d%d%d",&rect[n].x1,&rect[n].y1,&rect[n].x2,&rect[n].y2);
 		 if(rect[n].x1==-1)break;
		}
	printf("%I64d
",area());
 }
 return 0;
}