P1959 【遗址】

2018-09-06 11:48:46


%%%%troubler

原作者troubler亲笔.

他没实名

这道题一看就很水

好吧 ,听我一本正经地胡说八道

首先看到这道题以后, 点的个数 < 3000 ,于是很明显的想到了 O(N ^ 2) 的枚举

于是, 我们可以每两个点都建一条边 , 然后去找正方形

易知,在平面直角坐标系中一条边仅能扩展出两个正方形 (不信你可以试试 , 下面有图)(证明:一条直线将平面分割成两部分,一边各一个), 于是我们只要枚举边 , 再去找正方形就好了,如果存在 , 就计算面积 ,总的去一个MAX即可

看图(看不清的放大看):

这一部分的代码在 check 函数里面, 一一对应地看会找到规律 ;

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 ;
}

这个函数是用来找正方形的,然后剩下的就很简单了

贴上高清代码 (还有注释 , 很详尽) :

#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 ;
}