【POJ1151】Atlantis（线段树，扫描线）

时间：2022-05-19 23:25:20

【POJ1151】Atlantis（线段树，扫描线）

题面

Vjudge

题解

学一学扫描线

其实很简单啦

这道题目要求的就是若干矩形的面积和

把扫描线平行于某个轴扫过去（我选的平行\(y\)轴扫）

这样只需要求出每次和\(x\)轴覆盖的长度

就可以两两相乘，求出面积

最后累计和就行啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 500

#define lson (now<<1)

#define rson (now<<1|1)

struct Node{double x1,x2,y,w;}p[MAX];

bool operator<(Node a,Node b){return a.y<b.y;}

double S[MAX];

int top;

int n,tot;

struct SegmentTreeNode

{

	double ss;

	int ly;

}t[MAX<<3];

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

{

	if(t[now].ly)t[now].ss=S[r+1]-S[l];

	else if(l==r)t[now].ss=0;

	else t[now].ss=t[lson].ss+t[rson].ss;

}

void Modify(int now,int l,int r,int L,int R,int w)

{

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

	{

		t[now].ly+=w;

		pushup(now,l,r);

		return;

	}

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

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	pushup(now,l,r);

}

int main()

{

	int TT=0;

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

	{

		++TT;

		if(!n)break;

		tot=top=0;

		double x1,x2,y1,y2;

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

		{

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

			p[++tot]=(Node){x1,x2,y1,1};

			p[++tot]=(Node){x1,x2,y2,-1};

			S[++top]=x1,S[++top]=x2;

		}

		sort(&S[1],&S[top+1]);

		sort(&p[1],&p[tot+1]);

		top=unique(&S[1],&S[top+1])-S-1;

		double ans=0;

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

		{

			int l=lower_bound(&S[1],&S[top+1],p[i].x1)-S;

			int r=lower_bound(&S[1],&S[top+1],p[i].x2)-S-1;

			if(l<=r)Modify(1,1,top,l,r,p[i].w);

			if(i!=tot)ans+=(p[i+1].y-p[i].y)*t[1].ss;

		}

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

		memset(t,0,sizeof(t));

	}

	return 0;

}

相关文章