洛谷P1034 矩形覆盖

暴搜

因为 k<=4 所以爆搜一下就行

1、对于每个点 爆搜他属于哪一个矩形

2、并且 用这个点 来更新矩形的 左边界 右边界 上边界 下边界

3、回溯

优化 1、一边加入点一边判断是否符合要求

2、已有的矩形中是否有相互覆盖的情况

3、以及现在的矩形面积是否大于已有的 最小答案的矩形 如果是 说明不可能更优，那么就直接退出

 

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ; 10 11 inline int read() 12 {13 char ch = getchar() ; 14 int x = 0,f = 1 ; 15 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 16 while(ch>='0'&&ch<='9') { x = x*10 + ch - 48 ; ch = getchar() ; } 17 return x*f ; 18 }19 20 21 const int maxn = 51,inf = 1e9 ; 22 struct dot {23 int x,y ; 24 }d[51];25 struct node{26 dot l,r ; 27 }rec[5] ;28 int n,k,ans ; 29 30 inline int getS() 31 {32 int sum = 0 ; 33 for(int i=1;i<=k;i++) 34 {35 if(rec[ i ].l.x==inf ) continue ; 36 sum = sum + ( rec[ i ].r.x - rec[ i ].l.x ) * ( rec[ i ].r.y - rec[ i ].l.y ) ; 37 }38 return sum ; }39 40 41 inline bool conf(int i,int j) 42 {43 if( rec[ i ].l.x==inf ) 44 return 0 ; 45 if( rec[ j ].l.x==inf ) 46 return 0 ; 47 if( rec[ i ].r.x
             
              rec[ i ].r.x ) rec[ i ].r.x = d[used+1].x ; 74 if ( d[used+1].y
              
               rec[ i ].r.y ) rec[ i ].r.y = d[used+1].y ; 76 if ( can()&&getS()