【题解】codevs 3044 矩形面积合并

传送门

3044 矩形面积求并

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

输入n个矩形，求他们总共占地面积（也就是求一下面积的并）

输入描述 Input Description

可能有多组数据，读到n=0为止(不超过15组)

每组数据第一行一个数n，表示矩形个数(n<=100)

接下来n行每行4个实数x1,y1,x2,y1(0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000)，表示矩形的左下角坐标和右上角坐标

输出描述 Output Description

每组数据输出一行表示答案

样例输入 Sample Input

10 10 20 20

15 15 25 25.5

样例输出 Sample Output

180.00

数据范围及提示 Data Size & Hint

无

前言：

先是在《高级数据结构》上看到了这道例题，然而各种指针蒟蒻的我根本看不惯；昨天老师又讲了一下这道题，然而蒟蒻的我还是没懂。蒟蒻的我又看了一下黄学长（orz）的博客，然后......我就好像懂了。然而敲了一小时代码，运行时忽然发现卡入循环无法自拔，到今天早上忽然发现一个玄学错误，把二分查找带入一个参数终于能正常运行。然而又发现样例都过不了，又不断调试，调了一个小时，找了几处错误，终于AC了，要是在考场上我怕是要van了。
分析：

首先先不考虑什么离散化，线段树之类的，先想主要的算法。

我们假想一根扫描线（在这里假设它平行于x轴），从下往上扫，扫到一条边就在它在一根数轴上的投影上打上标记，假如已被覆盖那就只用加上标记，没被覆盖就还要让一个记录长度总和的变量加上长度，然后请用长度的总和乘以与下一条边的高度差。同时如果该边是矩形的上边的话那就在扫描后删去这条边的标记。

然后再逐一考虑细节，首先我们可以用数组暴力模拟覆盖标记过程，当然为了最优我们选择线段树。

接着就有一个大问题，它给出的坐标是实数而非整数，这样线段树树或数组就不可能对应x轴的每一个端点，怎么办呢？用离散化，首先我们是要搞一个数组存各个点的横纵坐标对吧，我们再搞一个数组node存各个横坐标，然后将这个node从小到大排序，我们就把这个node数组每一个下标看做线段的端点，实际上我们也知道小的下标存小的横坐标，大的下标存大的横坐标。虽然理解起来可能有点困难，但这确实是个非常有用的技巧。

同时我们还有一些问题要注意，每一次我们扫描是要知道这条新边的左右两个端点横坐标来加标记，所以我们可以在记录横纵坐标的数组里将两个横坐标都记录，再搞一个标记判断它是上边还是下边。
代码实现：

要是看不懂我这个蒟蒻写的话就看代码吧，多想多画几遍就理解了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=100010;

double sum[maxn<<2];

double node[maxn<<2];    //离散化，存x1，线段树的总区间是下标，

                      //但我们要给它排序，使得小的下标对小的x

					  //符合区间加法，这样才可以使用线段树

int n,k;

int ok[maxn<<1];//标记

int L,R;

double ans=0;

struct Dot{

	double x1,x2,y;

	short int opt;

}dot[maxn];

bool cmp(Dot a,Dot b){

	return a.y<b.y;

}

int binary_search(double t,int lim){

	int l=1,r=lim*2;

	int ans;

	while(l<=r)

	{

        int mid=(l+r)>>1;

		if(node[mid]==t){

			ans=mid;break;

		}

		else if(node[mid]>t)r=mid-1;

		else l=mid+1;

	}

	return ans;

}

void pushup(int now,int l,int r)

{

	if(ok[now])sum[now]=node[r+1]-node[l];

	else if(l==r)	sum[now]=0;//递归到叶节点且无覆盖

	else sum[now]=sum[now<<1]+sum[now<<1|1];

}

void update(int now,int l,int r)

{

	if(L<=l&&r<=R){

		ok[now]+=k;

		pushup(now,l,r);

		return ;

	}

	int mid=(l+r)>>1;

	if(L<=mid)update(now<<1,l,mid);

	if(R>mid)update(now<<1|1,mid+1,r);

	pushup(now,l,r);

	return;

}

int main()

{

	int n;

   	while(1){

   		double x1,x2,y1,y2;

   		scanf("%d",&n);

   		if(!n)return 0;

   		for(int i=1;i<=n;i++){

   			int d=(i<<1)-1,u=(i<<1);

   			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

   			dot[d].x1=x1;//下边

			dot[d].x2=x2;

			dot[d].y=y1;

			dot[d].opt=1;

			dot[u].x1=x1;//上边

			dot[u].x2=x2;

			dot[u].y=y2;

			dot[u].opt=-1;

			node[d]=x1;//离散化

			node[u]=x2;

   		}

   		sort(dot+1,dot+1+(n<<1),cmp);

   		sort(node+1,node+1+(n<<1));

   		for(int i=1;i<=(n<<1)-1;i++){

   			//debug		cout<<n<<endl;

		    L=binary_search(dot[i].x1,n);

		    R=binary_search(dot[i].x2,n)-1;

			//因为已离散化，我们需二分查找

           k=dot[i].opt;

		   update(1,1,2*n);

		   ans+=(dot[i+1].y-dot[i].y)*sum[1];

		}

		printf("%.2lf\n",ans);

		ans=0;              //一定要初始化

		memset(sum,0,sizeof(sum));

		memset(ok,0,sizeof(ok));

		memset(dot,0,sizeof(dot));

   	}

	return 0;

}

巴特西