POJ 1151 离散化线段树＋计算几何正矩形求并-白红宇

POJ 1151 离散化线段树＋计算几何正矩形求并

阅读量：7076 次

发布时间：2019-06-28

本文共 2491 字，大约阅读时间需要 8 分钟。

我觉得像我这样把所有东西都写的类的ACMer真是一个异类。。。

View Code

1 //Result:wizmann    1151    Accepted    832K    0MS    G++    3310B      2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
               11 #include 
               
                 12 13 using namespace std; 14 15 #define print(x) cout<
                
                 <
                 
                  >x 17 #define SIZE 128 18 19 struct node 20 { 21 int st,end; 22 double len; 23 int cov; 24 25 node(){} 26 node(int ist,int iend,double ilen) 27 { 28 cov=0; 29 st=ist;end=iend; 30 len=ilen; 31 } 32 33 bool equal(int a,int b) 34 { 35 return st==a && end==b; 36 } 37 38 int getmid() 39 { 40 return (st+end)>>1; 41 } 42 43 bool endnode() 44 { 45 return end-st<=1; 46 } 47 }; 48 49 struct point 50 { 51 double x,y; 52 point(){} 53 point(double i_x,double i_y) 54 { 55 x=i_x;y=i_y; 56 } 57 }; 58 59 struct segment 60 { 61 point p1,p2; 62 63 segment(){} 64 segment(const point& a,const point& b) 65 { 66 p1=a;p2=b; 67 } 68 }; 69 70 struct line 71 { 72 double y; 73 int x1,x2; 74 int flag; 75 line(){} 76 line(int ix1,int ix2,double iy,int iflag) 77 { 78 x1=ix1;x2=ix2; 79 y=iy;flag=iflag; 80 } 81 friend bool operator < (const line& a,const line& b) 82 { 83 return a.y
                  
                    hash; 93 map
                   
                     anti_hash; 94 int sz,ind; 95 line edge[SIZE<<1]; 96 97 98 inline int left(int x) 99 {100 return (x<<1)+1;101 }102 inline int right(int x)103 {104 return left(x)+1;105 }106 107 void stree_init(int l,int r,int pos=ROOT)108 {109 stree[pos]=node(l,r,anti_hash[r+1]-anti_hash[l]);110 if(l
                    
                     >1;113 stree_init(l,mid,left(pos));114 stree_init(mid+1,r,right(pos));115 }116 }117 118 void update(int l,int r,int cov,int pos=ROOT)119 {120 if(stree[pos].equal(l,r))121 {122 stree[pos].cov+=cov;123 }124 else125 {126 int mid=stree[pos].getmid();127 if(r<=mid) update(l,r,cov,left(pos));128 else if(l>mid) update(l,r,cov,right(pos));129 else130 {131 update(l,mid,cov,left(pos));132 update(mid+1,r,cov,right(pos));133 }134 }135 }136 137 double query(int pos=ROOT)138 {139 double res=0;140 if(stree[pos].cov>0) res+=stree[pos].len;141 else if(stree[pos].st!=stree[pos].end)142 {143 res+=query(left(pos));144 res+=query(right(pos));145 }146 return res;147 }148 149 int main()150 {151 double bx,by,ex,ey;152 int cas=1;153 while(input(n) && n)154 {155 hash.clear();156 anti_hash.clear();157 vector
                     
                       itemx;158 vector
                      
                        seg;159 for(int i=0;i