P1959 【遗址】

顾z

2018-09-06 11:48:46

Solution

## %%%%[troubler](https://www.luogu.org/space/show?uid=88089) **原作者troubler亲笔.** ~~他没实名~~ 这道题一看就很水~~难~~ 好吧 ,听我一本正经地胡说八道 首先看到这道题以后, 点的个数 < 3000 ,于是很明显的想到了 O(N ^ 2) 的枚举 于是, 我们可以每两个点都建一条边 , 然后去找正方形 ~~易知,~~在平面直角坐标系中一条边仅能扩展出两个正方形 (不信你可以试试 , 下面有图)(证明:一条直线将平面分割成两部分,一边各一个), 于是我们只要枚举边 , 再去找正方形就好了,如果存在 , 就计算面积 ,总的去一个MAX即可 看图(看不清的放大看): ![](https://i.loli.net/2018/09/06/5b90a021ca5b5.png) 这一部分的代码在 check 函数里面, 一一对应地看会找到规律 ; ```cpp ll check(ll xx , ll yy , ll zx , ll zy ) { ll cx = xx - zx , cy = yy - zy ; if( pd(xx + cy , yy - cx) && mmp[xx + cy][yy - cx] ) if( pd(zx + cy , zy - cx) && mmp[zx + cy][zy - cx] ) return cx * cx + cy * cy ; if( pd(xx - cy , yy + cx) && mmp[xx - cy][yy + cx] ) if( pd(zx - cy , zy + cx) && mmp[zx - cy][zy + cx] ) return cx * cx + cy * cy ; return 0 ; } ``` 这个函数是用来找正方形的,然后剩下的就很简单了 贴上高清代码 (还有注释 , 很详尽) : ```cpp #include<iostream> #include<cstdio> #define ll int #define E 3007 using namespace std ; ll n , ans ; ll x[E] , y[E] ; bool mmp[E << 1][E << 1] ; ll read() { ll s = 0 ; char ch ; while(!isdigit(ch = getchar())) ; for(s = ch - '0' ; isdigit(ch = getchar()) ; (s *= 10 ) += ch - '0') ; return s ; } bool pd(ll uu , ll vv) // 判断 当前点 有没有出界 { if(uu < 0 || uu > 5000)return 0 ; if(vv < 0 || vv > 5000)return 0 ; return 1 ; } ll check(ll xx , ll yy , ll zx , ll zy ) // 用我们在图中找到的规律寻找正方形 { ll cx = xx - zx , cy = yy - zy ; if( pd(xx + cy , yy - cx) && mmp[xx + cy][yy - cx] ) // 其实mmp 也可以写在pd函数里,判断当前坐标是否存在 点 if( pd(zx + cy , zy - cx) && mmp[zx + cy][zy - cx] ) return cx * cx + cy * cy ; // 如果在第一个时就成立 , 直接返回就好 , 因为就算第二个也成立,面积也是一样的 if( pd(xx - cy , yy + cx) && mmp[xx - cy][yy + cx] ) if( pd(zx - cy , zy + cx) && mmp[zx - cy][zy + cx] ) return cx * cx + cy * cy ; // 面积计算方法有多种证明方法 , 比较直观的就是 sqrt(cx*cx + cy*cy)^2 ; return 0 ; // 没找到 , 返回零 } int main() { n = read() ; for(int i = 1;i <= n; i ++) { x[i] = read() ; y[i] = read() ; mmp[x[i]][y[i]] = 1 ; } for(int i = 1 ; i <= n ; i ++) for(int j = 1; j < i ; j ++ ) ans = max( ans , check(x[i] , y[i] , x[j] , y[j] ) ) ; // 对答案求最大值 cout<< ans <<endl; return 0 ; } ```