joi2007ho_c

愚直にやるとO(N^4)でキツい

正方形の性質としてある1辺の長さと残りの3辺の長さが同じである

つまり任意の2点の距離が分かれば残りの2点は推測できるため,2点を調べるためのO(N^2)で済む

ここまでは分かってたのに

面積=a*a+b*b で済むところを sqrt(a*a+b*b)^2 ってやってたせいで小数点誤差してWA出しまくってた.

#include<bits/stdc++.h>

#define F first

#define S second

using namespace std;

int n;

bool c[5009][5009];

vector < pair<int, int> > vec;

int main(){

    cin >> n;

    for(int i=0;i<n;i++){

        int x, y;

        cin >> x >> y;

        c[x][y] = true;

        vec.push_back( make_pair(x, y) );

    }

    int ans = 0;

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            int a = vec[i].S - vec[j].S, b = vec[i].F - vec[j].F;

            int px = vec[i].F - a, py = vec[i].S + b;

            int qx = vec[j].F - a, qy = vec[j].S + b;

            if(px < 0 || py < 0 || qx < 0 || qy < 0) continue;

            if(px > 5000 || py > 5000 || qx > 5000 || qy > 5000) continue;

            if(c[px][py] && c[qx][qy]) ans = max(ans, a*a+b*b);

        }

    }

    cout << ans << endl;

}