| ||||||||||
| 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 | |||||||||
发个code纪念一下下#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=5555;
int n,m,tot;
struct lines
{
int mark;
double l,r,h;
lines(){}
lines(int mark,double l,double r,double h):mark(mark),l(l),r(r),h(h){}
inline bool operator < (const lines tmp) const
{
return h<tmp.h;
}
}line[MAXN<<1];
double x[MAXN<<1];
namespace stree
{
int sum[MAXN<<2];
double len[MAXN<<2];
inline void push_down(int k,int l,int r)
{
if (sum[k]) len[k]=x[r+1]-x[l];
else len[k]=len[k<<1]+len[k<<1|1];
}
inline void edit_tree(int k,int l,int r,double _l,double _r,int d)
{
int mid=l+r>>1;
if (_r<=x[l]||_l>=x[r+1]) return ;
if (_l<=x[l]&&_r>=x[r+1]) sum[k]+=d;
else edit_tree(k<<1,l,mid,_l,_r,d),edit_tree(k<<1|1,mid+1,r,_l,_r,d);
push_down(k,l,r);
}
}
int main()
{
double x1,x2,y1,y2;
int cas,t=0;
while (~scanf("%d",&n)&&n)
{
m=n<<1;
for (int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
x[(i<<1)-1]=x1;x[i<<1]=x2;
line[(i<<1)-1]=lines(1,x1,x2,y1);
line[i<<1]=lines(-1,x1,x2,y2);
}
double ans=0;
sort(x+1,x+m+1);
sort(line+1,line+m+1);
x[tot=1]=x[1];for (int i=2;i<=m;i++) if (x[i]!=x[i-1]) x[++tot]=x[i];
for (int i=1;i<m;i++)
{
stree::edit_tree(1,1,tot-1,line[i].l,line[i].r,line[i].mark);
ans+=stree::len[1]*(line[i+1].h-line[i].h);
}
stree::edit_tree(1,1,tot-1,line[m].l,line[m].r,line[m].mark);
printf("Test case #%d\n",++t);
printf("Total explored area: %.2f\n\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator