JOI2006/2007 最古の遺跡
問題概要
複数の座標が与えられ、それらの座標を結んでできる正方形のうち面積最大となるものの面積を求めよ。
制約
考察
解説通り二分探索で通している人が少なかったため、解説を残します。
まず、愚直に、点を全列挙する方法が浮かぶと思いますが、かかります。今回の制約では、となっているのでこのままだと通りません。 したがって、正方形の性質をうまく活用することで、計算量を落とすことを考えます。
正方形は、点が定まると、残りの点を求めることが可能です。
具体的には、上のような点があるとき、
となります。つまり、残り点の候補を全ての 2 点の組み合わせから調べ、候補が元の配列の中に含まれていれば良いということになります。
今回は、含まれているかどうかの判定に二分探索を使用しています。使用するために予め配列を sort しておきます。
以下がサンプルコードです。
sample.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int main() {
int n; cin >> n;
vector<P> p(n);
for(int i = 0; i < n; i++) {
cin >> p[i].first >> p[i].second;
}
sort(p.begin(), p.end());
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int xi, yi; xi = p[i].first, yi = p[i].second;
int xj, yj; xj = p[j].first, yj = p[j].second;
int xdif, ydif; xdif = xi - xj; ydif = yi - yj;
P q = make_pair(xi + ydif, yi - xdif);
P r = make_pair(xj + ydif, yj - xdif);
if(binary_search(p.begin(), p.end(), q) && binary_search(p.begin(), p.end(), r)) {
ans = max(ans, xdif*xdif + ydif*ydif);
}
}
}
cout << ans << endl;
return 0;
}