[Python] JOI 2007 Final 3 --Les ruines les plus anciennes ((1) Vecteur de mathématiques du lycée, (2) "dans la liste" est extrêmement lent) [At Coder]

[Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez 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)

C'est la 7ème question! difficile! !! !! J'ai fait de mon mieux pour le comprendre, alors je vais l'expliquer ~

Sélection finale JOI 2007 3-The Oldest Ruins

À partir du code AC en premier ↓

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)

Hama Repoint

Je pense qu'il existe deux types principaux. ** ① Connaissances préalables Vecteur de mathématiques du lycée ② La connaissance pour ne pas devenir TLE "dans la liste" est extrêmement lente! !! !! ** **

① Connaissances préalables Vecteur de mathématiques du lycée

D'abord des bases! ABC108B - Ruined Square difficulty:140 Il y a quatre sommets carrés. Le problème de trouver les deux points restants alors que seuls deux d'entre eux sont connus.

Dans le cas de l'exemple d'entrée / sortie 2

Bref, si vous voulez faire un carré ** Pour un vecteur Échangez x et y et ajoutez un moins à l'un ou l'autre! !! !! ** **

Dans ce numéro, il est écrit dans le sens antihoraire, donc Dans la figure ci-dessus, Trouvez les coordonnées x et y des sommets C et D, respectivement! (Vous n'avez pas à penser aux carrés sur les côtés E et F.) Un vecteur de même longueur et perpendiculaire au vecteur AB est (-3,4) Parce que c'est devenu Le sommet de C est la position de B (6,6) + (-3,4) → (3,10) Le sommet de D est la position de A (2,3) + (-3,4) → (-1,7) On dirait que tu peux y aller! Quand je le réveille dans le code, ça ressemble à ça!

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)

Sujet principal

Application du problème précédent (ABC108B)!

1. Obtenez le vecteur de toutes les combinaisons,
2. Obtenez un vecteur vertical pour chaque vecteur! → À ce moment-là, si X et Y montrés dans la figure ci-dessous chevauchent le vecteur vertical, il devient un carré! !! !!

Le reste est enthousiaste! N'ayez pas trop peur des vecteurs! ** Les vecteurs ne sont que des flèches! ** **

② La connaissance pour ne pas devenir TLE "dans la liste" est extrêmement lente! !! !!

Le code suivant sera TLE. (PyPy devient également 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)

** ↓ Cette partie est trop lourde ...! ** **

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

Article de référence ・ Quantité de calcul embarrassante si vous ne connaissez pas Pythonista ・ [Python] L'opérateur in est-il lent?

** Si vous vous souciez de la quantité de calcul, mettez set ou dict qui utilise une table de hachage après dans! ** ** Ensuite, changeons xy en set ~

Erreur d'exécution ... ** Sur la ligne 5, list ne peut pas être haché ... **

Article de référence Hashable en Python

En bref ** ・ ʻimmuable (ne peut pas être changé!) ʻInt, str, tuple, frozenset sont hashable · Liste n'est pas hachable ** Cela signifie!

str = 'abc'
#str est immuable, vous ne pouvez donc pas faire cela! !! !!
str[0] = 'x' 
#TypeError: 'str' object does not support item assignment

list = ['a','b','c']
list[0] = 'x' #Aucune erreur ne se produit!

Donc, ** L'entrée est hashable avec ʻimmuable au lieu de liste tuple`** Je te l'ai donné!

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)

Enfin, AC! !! !! Merci pour votre travail acharné ~

fin!