Atlantis poj1151 线段树扫描线

题意

题目给了n个矩形，每个矩形给了左下角和右上角的坐标，矩形可能会重叠，求的是矩形最后的面积。

题解思路

这个是我线段树扫描线的第一题，听了学长的讲解，仔细研读了学长的代码，也算初步入门。

这里我们竖着的扫描线，从左到右来进行扫描的。

线段树这里端点代表的是一个区间

这里的y范围比较大，所以咱们需要离散化。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define mid ((tre[rt].l+tre[rt].r)>>1)

#define ls (rt<<1)

#define rs (rt<<1|1)

using namespace std;

const int maxn=1e2+7;

struct node{ //四元组

	double x, y1, y2;

	int k; //左边的边k是1， 右边的k为-1

	bool friend operator < (node a, node b)

	{

		return a.x < b.x;

	}

}a[maxn<<1];

struct tree{

	int l, r, cnt; //cnt记录区间被标记的次数

	double len;

}tre[maxn<<3];

map<double, int> mp;

double raw[maxn<<1];

int n,num;

void build(int rt, int l, int r)

{

	tre[rt].l=l;

	tre[rt].r=r;

	tre[rt].len=tre[rt].cnt=0;

	if(l==r) return ;

	build(ls, l, mid);

	build(rs, mid+1, r);

}

void change(int rt, int l, int r, int k)

{

	if(l <= tre[rt].l && tre[rt].r <= r)

	{

		tre[rt].cnt+=k;

		if(tre[rt].cnt>0)

		{

			tre[rt].len=raw[tre[rt].r+1] - raw[tre[rt].l];

		}

		else if(tre[rt].l==tre[rt].r) //到达端点了

		{

			tre[rt].len=0;

		}

		else tre[rt].len=tre[ls].len+tre[rs].len;

		return ;

	}

	if(l <= mid) change(ls, l, r, k);

	if(r > mid) change(rs, l, r, k);

	tre[rt].len = tre[rt].cnt > 0 ? raw[tre[rt].r+1] - raw[tre[rt].l] : tre[ls].len+tre[rs].len;

}

int main()

{

	while(scanf("%d", &n) && n)

	{

		int cnt;

		double x1, y1, x2, y2;

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

		{

			cnt=i<<1;

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

			a[cnt-1].x=x1; a[cnt-1].y1=y1; a[cnt-1].y2=y2; a[cnt-1].k=1;

			a[cnt].x=x2; a[cnt].y1=y1; a[cnt].y2=y2; a[cnt].k=-1;

			raw[cnt-1]=y1; raw[cnt]=y2;

		}

		n<<=1;

		sort(raw+1, raw+1+n);

		int m=unique(raw+1, raw+n+1)-(raw+1);

		for(int i=1; i<=m; i++)

		{

			mp[raw[i]]=i;

		}

		sort(a+1, a+n+1);

		build(1, 1, m-1); //这里线段树的点记录的区域，因为有m个y，所以就相当于m-1个区域

		double ans=0;

		for(int i=1; i<n; i++) //只需要处理到倒数第二个点即可

		{

			int l=mp[a[i].y1], r=mp[a[i].y2]-1;

			change(1, l, r, a[i].k);

			ans += tre[1].len*(a[i+1].x - a[i].x);

		}

		printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);

	}

	return 0;

}

巴特西

Atlantis poj1151 线段树扫描线

Atlantis poj1151 线段树扫描线

题意

题解思路

代码实现

最新文章

热门文章