POJ 1151：Atlantis 线段树+扫描线

Description

Input

Output

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00 

题意是给出诸多矩形的左下角坐标和右上角坐标，问这些矩形一共覆盖的面积。

看了真的是很久很久，终于把这道题的代码搞懂了，趁着对这道题有很多感觉，赶紧记下来。也通过这些题，发现线段树的应用范围真的是广。

实际上就是对每一段的x，求其y的长度，相乘就是对应的面积。最后把所有的面积加起来就是总面积。为了防止可能会发生重复加的面积，使用了线段树的结构。

首先是离散化，把y坐标上的浮点数 变成1 2 3 ---，然后使用对每一条边使用二分查找。

然后线段树中的每一个节点就代表了相应段的y的长度，和之前的线段树一样，线段树的思想就是我要使用哪一段的长度，我再去计算它更新它，这里面的len就代表了这个含义。

然后就是cover，cover就是只有为0的时候去更新它，因为不是0的时候代表着它依然被某个矩形覆盖着，所以不能更新成子节点的长度之和。

dele就是将原来的长度划出掉，cover--，判断为0就更新该点的len。

写到哪里算哪里，看着这段代码，觉得真的很奇妙。

代码：

#pragma warning(disable:4996)  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring>
using namespace std;

double y[210];

struct li
{
	double x,y1,y2;
	bool bleft;
}lines[210];

struct no
{
	int L,R;
	double len;
	int cover;

}tree[10000];

bool operator < (const li &n1,const li &n2)
{
	return n1.x<n2.x;
}

template <class F,class T>
F bin_search(F s,F e,T val)
{
	F L = s;
	F R = e-1;

	while(L<=R)
	{
		F mid = L + (R-L)/2;
		if(!(*mid<val || val < *mid))
		{
			return mid;
		}
		else if(val < *mid)
		{
			R = mid -1;
		}
		else
		{
			L= mid + 1;
		}
	}
}

void buildtree(int root,int L,int R)
{
	tree[root].L=L;
	tree[root].R=R;

	tree[root].len=0;
	tree[root].cover=0;

	if(L!=R)
	{
		int mid = (L+R)/2;
		buildtree(root*2+1,L,mid);
		buildtree(root*2+2,mid+1,R);
	}
}

void inse(int root,int L,int R)
{
	if(tree[root].L==L&&tree[root].R==R)
	{
		tree[root].cover++;
		tree[root].len= y[R+1] - y[L];
		return;
	}
	int mid = (tree[root].L + tree[root].R)/2;
	
	if(R<=mid)
	{
		inse(root*2+1,L,R);
	}
	else if(L>=mid+1)
	{
		inse(root*2+2,L,R);
	}
	else
	{
		inse(root*2+1,L,mid);
		inse(root*2+2,mid+1,R);
	}
	if(tree[root].cover==0)
	{
		tree[root].len = tree[root*2+1].len + tree[root*2+2].len;
	}
}

void dele(int root,int L,int R)
{
	if(tree[root].L == L && tree[root].R == R)
	{
		tree[root].cover--;
		if(tree[root].cover==0)
		{
			if(tree[root].L == tree[root].R)
			{
				tree[root].len=0;
			}
			else
			{
				tree[root].len = tree[root*2+1].len + tree[root*2+2].len; 
			}
		}
		return;
	}

	int mid = (tree[root].L + tree[root].R)/2;
	if(R<=mid)
	{
		dele(root*2+1,L,R);
	}
	else if(L>=mid+1)
	{
		dele(root*2+2,L,R);
	}
	else
	{
		dele(root*2+1,L,mid);
		dele(root*2+2,mid+1,R);
	}

	if(tree[root].cover==0)
	{
		tree[root].len = tree[root*2+1].len + tree[root*2+2].len; 
	}
}
int n;

int main()
{	
	int i,yc,lc,t;
	double x1,x2,y1,y2;
	t=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		t++;
		yc=0;
		lc=0;
		for(i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			y[yc++]=y1;
			y[yc++]=y2;

			lines[lc].x=x1;
			lines[lc].y1=y1;
			lines[lc].y2=y2;
			lines[lc].bleft=true;
			lc++;

			lines[lc].x=x2;
			lines[lc].y1=y1;
			lines[lc].y2=y2;
			lines[lc].bleft=false;
			lc++;
		}
		sort(lines,lines+lc);
		sort(y,y+yc);
		yc=unique(y,y+yc)-y;

		buildtree(0,0,yc-1-1);
		double Area=0;

		for(i=0;i<lc-1;i++)
		{
			int L=bin_search(y,y+yc,lines[i].y1)-y;
			int R=bin_search(y,y+yc,lines[i].y2)-y;

			if(lines[i].bleft)
			{
				inse(0,L,R-1);
			}
			else
			{
				dele(0,L,R-1);
			}
			Area += tree[0].len*(lines[i+1].x-lines[i].x);
		}
		printf("Test case #%d
",t);
		printf("Total explored area: %.2lf
",Area);
		printf("
");
	}

	//system("pause");
	return 0;
}