最古の遺跡解説

この問題です

ジャッジ:C - 最古の遺跡
問題:https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf

オーダー的にO(N3)が辛くてO(N2)が通るので、O(N2)を考えます。 二点を固定して、残りの二頂点C,Dに点があるかを判定すれば良いです。
f:id:eiya5498513:20171008203034j:plain

まずは、C1,D1に頂点があるかを確認します。
この後はC1,D1をただC,Dと呼びます。

ここで予めある座標に頂点があるかどうかをbool配列でもっておくと、あとはC1,D1の座標を求めるだけであるなしが判定できます。

なんとなく正方形ABCDを回転していない正方形で囲ってみます。(なぜこの発想になるのかの説明は余裕があったら追記します...)
f:id:eiya5498513:20171008203947j:plain

x = Bx - Ax、y = By - Ayとなるようにx,yを取ります。そうするとx,yは上図のようになります。
ここで、三角形ABO1≡三角形CAO2なので、CO2==x、O2A==yです。
f:id:eiya5498513:20171008204448j:plain

よって、Cx = Ax - y、Cy = Ay + xで求められることが分かります。
又、DはDx = Cx + x、Dy = Cy + yで求まります。

この図はA->Bが右上がりの時の図なので、A->Bが右下がりの時どうなるか考えてみます。

どんどんBを下げていくと、こうなります。
f:id:eiya5498513:20171008205141j:plain
この時は三角形が作れないですが、無理やりy==0と考えてやると、上手く行くことが分かります。

Bをもっと下げてみます。
f:id:eiya5498513:20171008205336j:plain
図の形が変わりました。
xとyをそのまま負数に拡張してやると、図のようになり、式を変えずにそのまま計算することが出来ます。

xが負の時も同じように考えると、式を全く変形せずにCx = Ax - y、Cy = Ay + x、Dx = Cx + x、Dy = Cy + yの式で良いことが分かります。

次にC2,D2について考えます。
Aを中心にxとyを反転させる(Aを中心に紙を180度回す)と図のようになります。 回転後のBをA'、回転後のAをB'と考えると、C1',D1'がそれぞれC2,D2に対応します。
よって、「AとBを入れ替えてもう一度C1,D1を求める処理をする」とC2,D2の座標を求めることが出来ます。

ここで、C2,D2を求めるときに行っているのはAとBを交換する作業であることから、AとBの選び方をいつものように組み合わせを考えるときの以下のfor分

for(int a=0;a < N;++a)for(int b = a+1;b < N;++b)

を使うと思いますが、今回は

for(int a=0;a < N;++a)for(int b = 0;b < N;++b){
if(a==b){continue;}
//処理
}

とa,bの順番も考慮してやることで、C1,D1の座標を求めるコードのみにしてやることが出来ます。

ところで、a==bの時は何が起こるのでしょう。
この時は同じ頂点二つを使って正方形を作ろうとし、その4頂点は全て同じ座標に存在するので、正方形が作れてしまいます。
しかし実際は4頂点を選んで正方形を作らないといけないので、作ってはいけない正方形を作ってしまいます。これは弾く必要が有ります。
しかしよく考えると、この時正方形の面積は0、つまり正方形の最小の面積1よりも小さいので、実は「正方形が存在する場合は」弾いてやらなくても面積のmaxを取る段階で弾くことが出来ます。
逆に面積のmaxが0のときは正方形が一つも存在しないということなので、例外処理である0を出力する必要が有ります。
が、値が0の時に0を出力するという処理になっているので、結局そのまま出力すれば良いことが分かります。

この方針でコードを実装してやるとこうなります。短く書けるのでバグを埋め込みにくくなります。
Submission #1671065 - 第6回日本情報オリンピック 本選(オンライン)