hdu 1542/1255 Atlantis/覆盖的面积

1542

1255

两道扫描线+线段树的入门题。

基本没有什么区别，前者是模板，后者因为是求覆盖次数至少在两次以上的，这个同样是具有并集性质的，所以把cover的判断条件更改一下就可以了qwq。

hdu1542 代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200010

using namespace std;

int n,c,cnt;

double y[MAXN];

struct Node{

	double x,l,r;

	int cover;

	bool flag;

}node[MAXN];

struct Line

{

	double x,y_up,y_down;

	int flag;

}line[MAXN];

inline bool cmp(struct Line x,struct Line y){return x.x<y.x;}

inline int ls(int x){return x<<1;}

inline int rs(int x){return x<<1|1;}

inline void build(int x,int l,int r)

{

	node[x].l=y[l],node[x].r=y[r],node[x].x=-1,node[x].flag=false,node[x].cover=0;

	if(l+1==r){node[x].flag=true; return;}

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

	build(ls(x),l,mid);

	build(rs(x),mid,r);

}

inline double q_update(int x,double pos,double l,double r,int flag)

{

	if(l>=node[x].r||r<=node[x].l) return 0;

	if(node[x].flag)

	{

		if(node[x].cover<=0)

		{

			node[x].x=pos;

			node[x].cover+=flag;

			return 0;

		}

		double pre=node[x].x;

		double ans=(pos-pre)*(node[x].r-node[x].l);

		node[x].x=pos;

		node[x].cover+=flag;

		return ans;

	}

	return q_update(ls(x),pos,l,r,flag)+q_update(rs(x),pos,l,r,flag);

}

int main()

{

	scanf("%d",&n);

	while(n!=0)

	{

		double x1,x2,y1,y2;

		cnt=0;

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

		{

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

			line[++cnt].x=x1,line[cnt].y_down=y1,line[cnt].y_up=y2,line[cnt].flag=1,y[cnt]=y1;

			line[++cnt].x=x2,line[cnt].y_down=y1,line[cnt].y_up=y2,line[cnt].flag=-1,y[cnt]=y2;

		}

		sort(&line[1],&line[cnt+1],cmp);

		sort(&y[1],&y[cnt+1]);

		build(1,1,cnt);

		double ans=0;

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

			ans+=q_update(1,line[i].x,line[i].y_down,line[i].y_up,line[i].flag);

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

		scanf("%d",&n);

	}

	return 0;

}

hdu1255 代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200010

using namespace std;

int n,c,cnt,t;

double y[MAXN];

struct Node{

	double x,l,r;

	int cover;

	bool flag;

}node[MAXN];

struct Line

{

	double x,y_up,y_down;

	int flag;

}line[MAXN];

inline bool cmp(struct Line x,struct Line y){return x.x<y.x;}

inline int ls(int x){return x<<1;}

inline int rs(int x){return x<<1|1;}

inline void build(int x,int l,int r)

{

	node[x].l=y[l],node[x].r=y[r],node[x].x=-1,node[x].flag=false,node[x].cover=0;

	if(l+1==r){node[x].flag=true; return;}

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

	build(ls(x),l,mid);

	build(rs(x),mid,r);

}

inline double q_update(int x,double pos,double l,double r,int flag)

{

	if(l>=node[x].r||r<=node[x].l) return 0;

	if(node[x].flag)

	{

		if(node[x].cover<=1)

		{

			node[x].x=pos;

			node[x].cover+=flag;

			return 0;

		}

		double pre=node[x].x;

		double ans=(pos-pre)*(node[x].r-node[x].l);

		node[x].x=pos;

		node[x].cover+=flag;

		return ans;

	}

	return q_update(ls(x),pos,l,r,flag)+q_update(rs(x),pos,l,r,flag);

}

int main()

{

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d",&n);

		double x1,x2,y1,y2;

		cnt=0;

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

		{

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

			line[++cnt].x=x1,line[cnt].y_down=y1,line[cnt].y_up=y2,line[cnt].flag=1,y[cnt]=y1;

			line[++cnt].x=x2,line[cnt].y_down=y1,line[cnt].y_up=y2,line[cnt].flag=-1,y[cnt]=y2;

		}

		sort(&line[1],&line[cnt+1],cmp);

		sort(&y[1],&y[cnt+1]);

		build(1,1,cnt);

		double ans=0;

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

			ans+=q_update(1,line[i].x,line[i].y_down,line[i].y_up,line[i].flag);

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

	}

	return 0;

}

巴特西

hdu 1542/1255 Atlantis/覆盖的面积

1542

1255

最新文章

热门文章