[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 ~
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)
I think there are two main types. ** ① Prerequisite knowledge High school math vector (2) Knowledge for not becoming TLE "in list" is extremely slow! !! !! ** **
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)
Application of the previous problem (ABC108B)!
The rest is enthusiastic! Don't be afraid of vectors that much! ** Vectors are just arrows! ** **
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!