[Python] JOI 2007 Final 3 - Die ältesten Ruinen ((1) Mathematikvektor der High School, (2) "in Liste" ist extrem langsam) [At Coder]

[Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen 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)

Dies ist die 7. Frage! schwer! !! !! Ich habe mein Bestes versucht, um es zu verstehen, also werde ich es erklären ~

JOI 2007 Final Selection 3 - Die ältesten Ruinen

Vom AC-Code zuerst ↓

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

Ich denke, es gibt zwei Haupttypen. ** ① Voraussetzung Kenntnisse High School Mathematik Vektor ② Das Wissen, nicht TLE "in Liste" zu werden, ist extrem langsam! !! !! ** ** **

① Voraussetzung Kenntnisse High School Mathematik Vektor

Zuerst von den Grundlagen! ABC108B - Ruined Square difficulty:140 Es gibt vier Eckpunkte des Quadrats. Das Problem, die verbleibenden zwei Punkte zu finden, wenn nur zwei davon bekannt sind.

Bei Eingabe / Ausgabe Beispiel 2

Kurz gesagt, wenn Sie ein Quadrat machen möchten ** Für einen Vektor Tauschen Sie x und y aus und fügen Sie jedem ein Minus hinzu! !! !! ** ** **

In dieser Ausgabe wird es also gegen den Uhrzeigersinn geschrieben In der obigen Abbildung Finden Sie die x- und y-Koordinaten der Eckpunkte C und D! (Sie müssen nicht an die Quadrate auf der E- und F-Seite denken.) Ein Vektor gleicher Länge und senkrecht zum AB-Vektor ist (-3,4) Weil es wurde Der Scheitelpunkt von C ist die Position von B (6,6) + (-3,4) → (3,10) Der Scheitelpunkt von D ist die Position von A (2,3) + (-3,4) → (-1,7) Es sieht so aus, als könntest du gehen! Wenn ich es im Code aufwecke, sieht es so aus!

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)

Hauptthema

Anwendung des vorherigen Problems (ABC108B)!

1. Holen Sie sich den Vektor aller Kombinationen,
2. Holen Sie sich einen vertikalen Vektor für jeden Vektor! → Wenn zu diesem Zeitpunkt sowohl X als auch Y (siehe Abbildung unten) den vertikalen Vektor überlappen, wird er zu einem Quadrat! !! !!

Der Rest ist begeistert! Hab keine Angst vor Vektoren! ** Vektoren sind nur Pfeile! ** ** **

② Das Wissen, nicht TLE "in Liste" zu werden, ist extrem langsam! !! !!

Der folgende Code ist TLE. (PyPy wird auch zu 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)

** ↓ Dieser Teil ist zu schwer ...! ** ** **

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

Referenzartikel ・ Peinliche Menge an Berechnungen, wenn Sie Pythonista nicht kennen ・ [Python] Ist der In-Operator langsam?

** Wenn Sie sich für den Rechenaufwand interessieren, setzen Sie "set" oder "dict", das eine Hash-Tabelle verwendet, nach in! ** ** ** Dann ändern wir xy in set ~

Laufzeit Fehler ... ** In Zeile 5 kann list nicht gehasht werden ... **

Referenzartikel Hashable in Python

Zusamenfassend ** · unveränderlich (kann nicht geändert werden!) Int, str, tuple, frozenset sind hashable · List ist nicht hashable ** Das bedeutet!

str = 'abc'
#str ist unveränderlich, also kannst du das nicht tun! !! !!
str[0] = 'x' 
#TypeError: 'str' object does not support item assignment

list = ['a','b','c']
list[0] = 'x' #Es tritt kein Fehler auf!

Deshalb, ** Die Eingabe ist "hashable" mit "unveränderlich" anstelle von "list" tuple** Ich habe es dir gegeben!

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)

Endlich AC! !! !! Vielen Dank für Ihre harte Arbeit ~

Ende!