競プロ初中級者100問

JOI2007本戦C 最古の遺跡

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c
https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf#page=5
この問題は全探索を用いて解くことができます。

方針

愚直な全探索はO(n^4)となり間に合いません。
そこで2点p1,p2を考え、時計回りに正方形を作ります。この時、残りの2つの点p3,p4は一意に定まります。
つまり、全ての2点の組み合わせp1,p2に対して、p3,p4が存在するかどうかを調べれば良いです。
存在の確認をハッシュテーブルなどでO(1)で実現できれば、問題を計算量O(n^2)で解くことができます。

Pythonの場合、setやdictはハッシュテーブルで実装されています。

あらかじめ点の組み合わせをソートしておくことで、2点の順列ではなく2点の組み合わせを考えれば良くなり、2倍高速になります。
三平方の定理を使うことで、正方形の面積は(x1-x2)**2+(y1-y2)**2で表せることがわかります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from itertools import combinations
N = int(input())
ls = []
for n in range(N):
    x, y = map(int,input().split())
    ls.append((x,y))
ls.sort()
st = set(ls)
ans = 0
for p1, p2 in combinations(ls, 2): # 組み合わせでOK
    x1, y1 = p1
    x2, y2 = p2
    if (x2 + y2 - y1, y2 + x1 - x2) in st and (x1 + y2 - y1, y1 + x1 - x2) in st:
        ans = max(ans, (x1-x2)**2+(y1-y2)**2)
print (ans)

記事情報

  • 投稿日：2020年5月7日
  • 最終更新日：2020年5月8日