[Python] JOI 2007 Final 3 --The oldest ruins ((1) High school math vector, (2) "in list" is extremely slow) [At Coder]

[Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( 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)

This is the 7th question! difficult! !! !! I tried my best to understand it, so I will explain it ~

JOI 2007 Final Selection 3-The Oldest Ruins

From the AC code first ↓

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)

Hamazushi Point

I think there are two main types. ** ① Prerequisite knowledge High school math vector (2) Knowledge for not becoming TLE "in list" is extremely slow! !! !! ** **

① Prerequisite knowledge High school math vector

First from the basics! ABC108B - Ruined Square difficulty:140 There are four vertices of the square. The problem of finding the remaining two points when only two of them are known.

In case of input / output example 2

In short, if you want to make a square ** For one vector Swap x and y and add a minus to either one! !! !! ** **

In this issue, I wrote counterclockwise, so In the figure above, Find the x and y coordinates of the vertices C and D, respectively! (You don't have to think about the squares on the vertices E and F sides.) A vector of the same length and perpendicular to the AB vector (-3,4) Because it became The vertex of C is the position of B (6,6) + (-3,4) → (3,10) The vertex of D is the position of A (2,3) + (-3,4) → (-1,7) It looks like you can go! When I wake it up in the code, it looks like this!

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)

Main subject

Application of the previous problem (ABC108B)!

1. Get the vector of all combinations,
2. Get a vertical vector for each vector! → At that time, if both X and Y shown in the figure below overlap the vertical vector, it becomes a square! !! !!

The rest is enthusiastic! Don't be afraid of vectors that much! ** Vectors are just arrows! ** **

(2) Knowledge for not becoming TLE "in list" is extremely slow! !! !!

The following code will be TLE. (PyPy also becomes TLE.)

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)

** ↓ This part is too heavy ...! ** **

if (x1-vectory,y1+vectorx) in xy and (x2-vectory,y2+vectorx) in xy:

Reference article ・ The amount of calculation that is embarrassing if you do not know Pythonista ・ [Python] Is the in operator slow?

** If you care about the amount of calculation, put set or dict that uses a hash table after in! ** ** Then, let's change xy to set ~

Runtime error ... ** On line 5, list cannot be hashed ... **

Reference article Hashable in Python

In short ** ・ ʻimmutable (cannot be changed!) ʻInt, str, tuple, frozenset are hashable · List is not hashable ** That means!

str = 'abc'
#str is immutable, so you can't do this! !! !!
str[0] = 'x' 
#TypeError: 'str' object does not support item assignment

list = ['a','b','c']
list[0] = 'x' #No error occurs!

Therefore, ** Input is hashable with ʻimmutable instead of list tuple`** I gave it to you!

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)

Finally, AC! !! !! Thank you for your hard work~

end!