【Python】JOI 2007 本選 3 - 最古の遺跡(①高校数学ベクトル、②「in リスト」は激遅)【AtCoder】

[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)(@e869120さん)

こちらの7問目！
難しい！！！
頑張って理解できたので解説〜

#[JOI 2007 本選 3 - 最古の遺跡](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c)
先にACコードから↓

```python:test.py
def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
n = I()
xy = [TI() for _ in range(n)]
set_xy = set(xy)
ans = 0
for i in range(n):
    x1,y1 = xy[i]
    for j in range(i+1,n):
        x2,y2 = xy[j]
        vectorx,vectory = x2-x1,y2-y1
        if (x1-vectory,y1+vectorx) in set_xy and (x2-vectory,y2+vectorx) in set_xy:
            ans = max(ans,vectorx**2+vectory**2)
print(ans)
```
#はまリポイント
大きく2つあると思います。
**①前提知識 高校数学ベクトル
②TLEにならないための知識 「in リスト」は激遅！！！**

##①前提知識 高校数学ベクトル
まず基本から!
### [ABC108B - Ruined Square](https://atcoder.jp/contests/abc108/tasks/abc108_b)
difficulty:140
正方形の頂点4つある。
そのうち2点だけわかっている時の残りの2点を求める問題。

入出力例2の場合
![IMG_9702.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/c00fc84f-0426-477b-1eba-18ea1ac6fe2f.jpeg)

要は、正方形を作りたければ、
**1つのベクトルに対して、
xとyを入れ替えてどっちかにマイナスつければいい！！！**

今回の問題では、反時計回りと書いているので、
上の図でいくと、
頂点C,Dのそれぞれx座標、y座標を求めれば良さそう！
(頂点E,F側の正方形は考えなくていい。)
ABベクトルに同じ長さで垂直なベクトルは、
(-3,4)
となったので、
Cの頂点は、Bの位置(6,6)+(-3,4)→(3,10)
Dの頂点は、Aの位置(2,3)+(-3,4)→(-1,7)
でいけそう！
コードにおこすとこんな感じ！

```python:test.py
def LI(): return list(map(int,input().split()))
x1,y1,x2,y2 = LI()
vector = (x2-x1,y2-y1)
x3,y3 = x2-vector[1],y2+vector[0]
x4,y4 = x1-vector[1],y1+vector[0]
print(x3,y3,x4,y4)
```
### 本題
先ほどの問題(ABC108B)の応用！
1.すべての組み合わせのベクトルを出し、
2.そのぞれぞれのベクトルに対して、垂直ベクトルを出す！
 →そのとき、垂直ベクトルの先に下図で言うXとYが2つとも重なれば、正方形となる！！！
![IMG_7156.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/c1dd5a2b-00d8-5d8c-e5b6-cdf4911ba7dc.jpeg)

後は気合！
そこまでベクトルを恐ることはない！
**ベクトルはただの矢印だ！**

##②TLEにならないための知識 「in リスト」は激遅！！！
以下のコードだと、TLEになる。(PyPyでも同じくTLEになる。)

```python:TLE.py
def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = int(input())
xy = [LI() for _ in range(n)]
ans = 0
for i in range(n):
    x1,y1 = xy[i][0],xy[i][1]
    for j in range(i+1,n):
        x2,y2 = xy[j][0],xy[j][1]
        vectorx,vectory = x2-x1,y2-y1
        if (x1-vectory,y1+vectorx) in xy and (x2-vectory,y2+vectorx) in xy:
            ans = max(ans,vectorx**2+vectory**2)
print(ans)
```

**↓この部分が重たすぎるのだ・・・！**

```python
if (x1-vectory,y1+vectorx) in xy and (x2-vectory,y2+vectorx) in xy:
```
参考の記事
[・Pythonistaなら知らないと恥ずかしい計算量のはなし](https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb)
[・【python】in演算子は遅いのか？](https://www.haya-programming.com/entry/2018/04/04/121458)

**計算量を気にするときは、inの後ろは、ハッシュテーブルを使ってる`set`や`dict`にしよう！**
じゃあ、xyを`set`にしてあげようね〜

<img width="879" alt="スクリーンショット 2020-04-19 2.04.11.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/fd08d649-f52b-9f8b-7e17-f1e2af3ea5d4.png">

実行時エラー・・・
**5行目で、`list`はハッシュ化できませんだと・・・**

参考の記事
[Python における hashable](https://qiita.com/yoichi22/items/ebf6ab3c6de26ddcc09a)

要は、
**・`immutable`(変えられない！)である`int`, `str`, `tuple`, `frozenset` は `hashable`
・`list`は、`hashable`ではない**
ということ！

```python
str = 'abc'
# strは、immutableなので、こんなことできない！！！
str[0] = 'x' 
#TypeError: 'str' object does not support item assignment

list = ['a','b','c']
list[0] = 'x' #エラーは起きない！
```

よって、
**入力のところを`list`ではなく、`immutable`で`hashable`な
`tuple`**
にしてあげた！


```python
def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
n = I()
xy = [TI() for _ in range(n)]
set_xy = set(xy)
```

やっとのことで、AC！！！
お疲れ様でした〜

おわり！