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