| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
线段树水之!!!!!#include <stdio.h>
#include <iostream>
#include <algorithm>
#define M 400+44
using namespace std;
struct note
{
int left;
int right;
int cover;
double len;
double ly,ry;
}tree[M*4];
struct Line
{
double x,y1,y2;
int flag;
}line[M];
double y[M];
bool cmp(Line a,Line b)
{
return a.x<b.x;
}
void build(int l,int r,int i)
{
tree[i].left=l;
tree[i].right=r;
tree[i].cover=0;
tree[i].len=0;
tree[i].ly=y[l];
tree[i].ry=y[r];
if(l+1==r) return;
int mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid,r,i<<1|1);
};
void update(int i,Line line1)
{
if(tree[i].ly>=line1.y1&&tree[i].ry<=line1.y2)
{
tree[i].cover+=line1.flag;
if(tree[i].cover>0)
{
tree[i].len=tree[i].ry-tree[i].ly;
}
else if(tree[i].left+1==tree[i].right)
{
tree[i].len=0;
}
else
{
tree[i].len=tree[i<<1].len+tree[i<<1|1].len;
}
return;
}
if(line1.y1>=tree[i<<1|1].ly) update(i<<1|1,line1);
else if(line1.y2<=tree[i<<1].ry) update(i<<1,line1);
else
{
update(i<<1|1,line1);
update(i<<1,line1);
}
if(tree[i].cover==0)
tree[i].len=tree[i<<1].len+tree[i<<1|1].len;
}
int main()
{
int N;
int o=0;
while(cin>>N,N)
{
int t=1,j=1,p=0;
for(int i=1;i<=N;i++)
{
double a,b,c,d;
cin>>a>>b>>c>>d;
y[j++]=b;
y[j++]=d;
line[t].flag=1;
line[t].x=a;
line[t].y1=b;
line[t].y2=d;
t++;
line[t].flag=-1;
line[t].x=c;
line[t].y1=b;
line[t].y2=d;
t++;
}
sort(y+1,y+t);
sort(line+1,line+t,cmp);
double s=0.0;
build (1,t-1,1);
update(1,line[1]);
for(int i=2;i<t;i++)
{
s+=tree[1].len*(line[i].x-line[i-1].x);
update(1,line[i]);
}
if(o!=0)
printf("\n");
printf("Test case #%d\nTotal explored area: ",++o);
printf("%.2f\n",s);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator