本文主要是介绍hud 1542——Atlantis hdu，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
扫描线问题
第一道扫描线，还是照着别人代码搞了一下。
树的内容不多，所以没放进结构体内。
map的映射挺方便，效率也不会很差。
//0MS 368K G++
#include<map>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 205
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
struct line
{
double l,r;
double h;
int flag;
line(){}
line(double a,double b,double c,int d):l(a),r(b),h(c),flag(d){}
}a[maxn<<1];
double x[maxn<<1];//从区间的左起点的横坐标
int cover[maxn<<2]; //整个区间被覆盖的次数 如果没有完全覆盖 赋值0
double sum[maxn<<2]; //整个区间被覆盖的长度
int cnt,k;
bool cmp(const line &a,const line &b)
{
return a.h<b.h;
}
void pushup(int l,int r,int rt)
{
if(cover[rt]) sum[rt] = x[r+1]-x[l];
else if(l==r) sum[rt]=0;
else sum[rt]=sum[ls]+sum[rs];
}
void change(int c,int L,int R, int l,int r,int rt)
{
if(L==l&&R==r)
{
cover[rt]+=c;
pushup(l,r,rt);
return;
}
if(R<=mid)
change(c,L,R, l,mid,ls);
else if(L>mid)
change(c,L,R, mid+1,r,rs);
else
{
change(c,L,mid, l,mid,ls);
change(c,mid+1,R, mid+1,r,rs);
}
pushup(l,r,rt);
}
int main()
{
int n;
double x1,x2,y1,y2;
int c=1;
while(~scanf("%d",&n),n)
{
cnt=0;
k=0;
map<double,int> m;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
a[cnt++]=line(x1,x2,y1,1);
a[cnt++]=line(x1,x2,y2,-1);
if(m[x1]==0) m[x1]=++k;
if(m[x2]==0) m[x2]=++k;
}
map<double,int>::iterator iter;
k=0;
for(iter=m.begin();iter!=m.end();iter++)
{
x[++k]=iter->first;
iter->second=k;
}
//build(1,1,k);
memset(sum,0,sizeof(sum));
memset(cover,0,sizeof(cover));
sort(a,a+cnt,cmp);
double ans=0.0;
for(int i=0;i<cnt-1;i++)
{
int l=m[a[i].l];//指的是以这个点为起点的区间编号
int r=m[a[i].r]-1;//右边的区间标号应-1
change(a[i].flag,l,r, 1,k-1,1);
ans+=sum[1]*(a[i+1].h-a[i].h);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",c++,ans);
}
return 0;
}
这篇关于hud 1542——Atlantis hdu的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
