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 |
orz二维树状数组的神犇In Reply To:【x和y分别离散化】然后就用二维树状数组搞定的。O(∩_∩)O哈哈~ Posted by:WilliamACM at 2013-02-16 19:14:15 > #include <stdio.h> > #include <iostream> > #include <algorithm> > #include <math.h> > #include <string.h> > #include <vector> > using namespace std; > const double eps=1e-12; > const int N=209; > struct node > { > double ox,oy; > int x,y; > }; > struct rect > { > node s,t; > }a[N]; > int n,cnta,cntb; > double ar[500],br[500]; > double backa[500],backb[500]; > int bina(double x) > { > int s=0,t=cnta-1; > while(s<=t) > { > int mid=(s+t)>>1; > if(fabs(ar[mid]-x)<eps) return mid+1; > if(ar[mid]>x) t=mid-1; > else s=mid+1; > } > } > int binb(double x) > { > int s=0,t=cntb-1; > while(s<=t) > { > int mid=(s+t)>>1; > if(fabs(br[mid]-x)<eps) return mid+1; > if(br[mid]>x) t=mid-1; > else s=mid+1; > } > } > int M[N][N]; > void add(int i,int j,int v) > { > for(;i<N;i+=-i&i) > { > int tj=j; > for(;tj<N;M[i][tj]+=v,tj+=-tj&tj); > } > } > int sum(int i,int j) > { > int ans=0; > for(;i;i-=-i&i) > { > int tj=j; > for(;tj;ans+=M[i][tj],tj-=-tj&tj); > } > return ans; > } > void rect_add(int x1,int y1,int x2,int y2) > { > add(x1,y1,1); > add(x1,y2+1,-1); > add(x2+1,y1,-1); > add(x2+1,y2+1,1); > } > void init() > { > int numa=0,numb=0; > memset(M,0,sizeof(M)); > for(int i=0;i<n;i++) > { > scanf("%lf%lf%lf%lf",&a[i].s.ox,&a[i].s.oy,&a[i].t.ox,&a[i].t.oy); > ar[numa++]=a[i].s.ox; > br[numb++]=a[i].s.oy; > ar[numa++]=a[i].t.ox; > br[numb++]=a[i].t.oy; > } > cnta=1; > for(int i=1;i<numa;i++) > if(fabs(ar[i]-ar[cnta-1])>eps) ar[cnta++]=ar[i]; > sort(ar,ar+cnta); > for(int i=0;i<cnta;i++) > backa[i+1]=ar[i]; > cntb=1; > for(int i=1;i<numb;i++) > if(fabs(br[i]-br[cntb-1])>eps) br[cntb++]=br[i]; > sort(br,br+cntb); > for(int i=0;i<cntb;i++) > backb[i+1]=br[i]; > > for(int i=0;i<n;i++) > { > a[i].s.x=bina(a[i].s.ox); > a[i].s.y=binb(a[i].s.oy); > a[i].t.x=bina(a[i].t.ox); > a[i].t.y=binb(a[i].t.oy); > rect_add(a[i].s.x,a[i].s.y,a[i].t.x-1,a[i].t.y-1); > } > double ans=0; > for(int i=1;i<cnta;i++) > for(int j=1;j<cntb;j++) > if(sum(i,j)) > { > double mx=backa[i+1]-backa[i]; > double my=backb[j+1]-backb[j]; > ans+=mx*my; > } > printf("%.2f\n\n",ans); > } > int main() > { > //freopen("in.txt","r",stdin); > int cnt=1; > while(scanf("%d",&n),n) > { > printf("Test case #%d\nTotal explored area: ",cnt++); > init(); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator