扫描线与悬线-白红宇

扫描线与悬线

阅读量：4972 次

发布时间：2019-06-12

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

好像很水....

但我就是想不到QAQ.......

AC VIJOS 1055 奶牛浴场

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 db eps=1e-20; 44 inline bool feq(db a,db b) 45 { return fabs(a-b)
                   
                     48 inline Type avg(const Type a,const Type b) 49 { return a+((b-a)/2); } 50 51 52 //============================================================================== 53 //============================================================================== 54 //============================================================================== 55 //============================================================================== 56 57 58 59 int xlim,ylim; 60 int n; 61 62 struct point{ int x,y; point(int x=0,int y=0):x(x),y(y){} }; 63 64 bool cmpx(const point&a,const point&b) 65 { return a.x!=b.x ? a.x
                    
                     a[i].x) b=a[j].x; 98 else 99 { t=b=a[i].x; break; }100 }101 res=max(res,(ylim-a[i].y)*(b-t));102 }103 //right to left scanning.104 for(int i=n-1;i>=0;i--)105 { 106 int t=0; //top limit107 int b=xlim; //bottom limit108 for(int j=i-1;j>=0;j--) //point-defined left limit scan.109 if(t<=a[j].x && a[j].x<=b)110 {111 res=max(res,(a[i].y-a[j].y)*(b-t));112 if(a[j].x
                     
                      a[i].x) b=a[j].x;115 else116 { t=b=a[i].x; break; }117 }118 res=max(res,a[i].y*(b-t));119 }120 121 //top-bottom scannin;122 if(n>=1)123 {124 stable_sort(a,a+n,cmpx);125 res=max(res,a[0].x*ylim); //first126 res=max(res,(xlim-a[n-1].x)*ylim); //last127 for(int i=1;i

View Code

扫描线.

扫描的目的是"枚举所有的极大子矩形".详见 .....

我们枚举确定某些极大子矩形左端界的点,然后从左到右维护这个极大子矩形的上下界.

注意维护的时候要保证所得到的上下界形成的矩形确实是以枚举的点作左端界点.

并且对于每个点,要对题目给出的边界进行特判.

并且还要反方向扫一遍.

并且还要在与扫描线垂直的方向,把所有左/右边界由题目给出边界确定的极大子矩形枚举一遍.

可以证明这样做以后所有的极大子矩形都被枚举掉了....

AC VIJOS 1351 棋盘制作

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 db eps=1e-20; 44 inline bool feq(db a,db b) 45 { return fabs(a-b)
                   
                     48 inline Type avg(const Type a,const Type b) 49 { return a+((b-a)/2); } 50 51 52 //============================================================================== 53 //============================================================================== 54 //============================================================================== 55 //============================================================================== 56 57 58 int n,m; 59 60 int M[2050][2050]; 61 62 int lmx[2050][2050]; 63 int rmx[2050][2050]; 64 65 int tmx[2050][2050]; 66 67 int res1=0,res2=0; 68 69 int main() 70 { 71 n=getint(); 72 m=getint(); 73 74 for(int i=0;i
                    
                     =0;j--) 86 rmx[i][j]=( M[i][j]!=M[i][j+1] ? rmx[i][j+1]+1 : 0 ); 87 } 88 89 for(int j=0;j

View Code

悬线法.

枚举每条悬线,找到可以拓展的左右端界然后计算答案更新答案.

左右的可扩展范围可以预处理+递推出来.

预处理出所有点往左往右的可扩展范围.递推的时候根据点的信息,从上到下维护整条悬线的可扩展范围.

悬线的好处就在于,预处理的时候就按照行列把每个点处理成"障碍点"或"非障碍点". 扫描线如果不做预处理,细节上会神坑(大神轻拍).

可以证明所有的极大子矩形都能够由一条悬线扩展而来.

这样我们就根据上面的方法枚举了所有的极大子矩形.

写的时候注意我们枚举的是悬线,因此一但扫到了障碍点要及时将左右端界扩展到最大的可行界.

剩下的就是细节问题.......下标略感混乱.......

AC USACO 2015 Jan. Gold T1 Cow Rectangles

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 db eps=1e-20; 44 inline bool feq(db a,db b) 45 { return fabs(a-b)
                   
                     48 inline Type avg(const Type a,const Type b) 49 { return a+((b-a)/2); } 50 51 52 //============================================================================== 53 //============================================================================== 54 //============================================================================== 55 //============================================================================== 56 57 58 int n; 59 60 int vx[505],xlim; 61 int vy[505],ylim; 62 struct point 63 { 64 int x,y; char type; 65 point(int x=-1,int y=-1,char t=' '):x(x),y(y),type(t){} 66 }; 67 68 point a[505]; 69 70 bool cmpx(const point&a,const point&b) 71 { return a.x==b.x ? a.y
                    
                     =res) 78 { 79 if(cnt>res) res=cnt,resS=S; 80 else resS=min(resS,S); 81 } 82 } 83 84 point x[505]; 85 bool able[505]; 86 87 int main() 88 { 89 freopen("cowrect.in","r",stdin); 90 freopen("cowrect.out","w",stdout); 91 92 n=getint(); 93 94 for(int i=0;i
                     
                      =0;i--)128 if(x[i].type=='G' || (i!=t-1 && x[i+1].x==x[i].x && x[i+1].type=='G'))129 able[i]=false;130 131 int last=0;132 while(!able[last] && last