今天学到了代码以外的东西，就是你在vj上挂了content ，然后你想更新它，你就要刷新一下，不然你提交的那题可能提交到别的地方。

好了回到重点，本题的题意是：

#include
     
      #define de(x) cout<<#x<<"="<
      
       <
       
        =(b);--i)#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)#define ll long long#define mt(a,b) memset(a,b,sizeof(a))#define fi first#define se second#define inf 0x3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define pii pair
        
         #define pdd pair
         
          #define pdi pair
          
           #define mp(u,v) make_pair(u,v)#define sz(a) a.size()#define ull unsigned long long#define ll long long#define pb push_back#define PI acos(-1.0)#define qc std::ios::sync_with_stdio(false)const int mod = 1e9+7;const int maxn = 1e6+9;const double EPS = 1e-6;using namespace std;struct Point{ int x,y;}p[maxn];bool cmp1(Point a,Point b){ return a.x
           
            ans){ ans = min(p[j].x-lx,r-l); ansl = lx; ansr = l; } if(p[i].y==p[j].y) break; if(p[i].y
            
             ans){ ans = min(lx-p[j].x,r-l); ansl = p[j].x; ansr = l; } if(p[i].y==p[j].y) break; if(p[i].y
             
              ans){ ans = min(w,p[i].y-p[i-1].y); ansl = 0; ansr = p[i-1].y; } } } printf("%d %d %d\n",ansl,ansr,ans); if(T) cout<
             
            
           
          
         
        
       
      
     

 

求一个最大正方形，边界可以包含障碍点，内部不能。

解法：

可以看看这个论文：http://www.doc88.com/p-9042008501060.html

我们可以用单调栈来做，但是复杂度是O(nm)，不能，但是我们可以用另一个方法，就是那个网站里的算法一，复杂度为O(s*s)，s为障点数；

做法就是先加入0,0和w，h这两个点（可以阻止第一类遗漏），先按x坐标排序，枚举每一个左边界，然后在反过来，枚举每一个右边界

然后接着就是矩形左边界和最左重合，右边界和最右重合的情况我门还是遗漏了，所以我们可以按y拍个序，枚举每两个y之间的矩形

代码：