HDu 1542走査線
20933 ワード
コード:
#include
#include
using namespace std;
const int maxn = 300+5;
double v[maxn];
//
struct L
{
double x;
double y1, y2;
int state;
bool operator<(L oth) {return x<oth.x;}
}line[maxn<<1];
//
struct Node
{
double l,r;
int cover;//
double len;//
}sgt[maxn<<3];
inline int ls(int k) {return k<<1;}
inline int rs(int k) {return k<<1|1;}
void pushup(int k)
{
if(sgt[k].cover) sgt[k].len=sgt[k].r-sgt[k].l;
else sgt[k].len=sgt[ls(k)].len+sgt[rs(k)].len;
}
void build(int l,int r,int k=1)
{
sgt[k].l=v[l],sgt[k].r=v[r],sgt[k].len=0,sgt[k].cover=0;
if(r<=l+1) return ;
int m=(l+r)>>1;
build(l,m,ls(k));
build(m,r,rs(k));
pushup(k);
}
void modify(double x,double y,int d,int k=1)
{
double l=sgt[k].l,r=sgt[k].r;
if(x<=l&&y>=r)
{
sgt[k].cover+=d;
pushup(k);
return ;
}
if(x<sgt[ls(k)].r) modify(x,y,d,ls(k));
if(y>sgt[rs(k)].l) modify(x,y,d,rs(k));
pushup(k);
}
int main()
{
double a,b,c,d;
int n;
int o=0;
while(~scanf("%d",&n))
{
if(n==0) break;
line[0]=(L){0,0,0,0};
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
v[i]=b,v[n+i]=d;
line[i]=(L){a,b,d,1},line[n+i]=(L){c,b,d,-1};
}
sort(line+1,line+1+(n<<1));
sort(v+1,v+1+(n<<1));
build(1,n<<1);
double ans=0;
for(int i=1;i<=n<<1;i++)
{
ans+=sgt[1].len*(line[i].x-line[i-1].x);
modify(line[i].y1,line[i].y2,line[i].state);
}
printf("Test case #%d
Total explored area: %.2lf
",++o,ans);
}
return 0;
}