Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

orz二维树状数组的神犇

Posted by lpl1998 at 2014-07-31 16:03:25 on Problem 1151
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator