Rekonstruktion eines konvexen Polygons aus einer Menge von Abständen

Python Hard math

Aufgabe «Rekonstruktion eines konvexen Polygons aus einer Menge von Abständen»

Gegeben ist eine Menge von N Punkten in der Ebene, die in der Reihenfolge des Durchlaufs ein konvexes Polygon bilden. Bekannt sind alle paarweisen Abstände zwischen den Eckpunkten, aber die Reihenfolge der Punkte ist unbekannt. Es ist erforderlich, die ursprüngliche Reihenfolge der Eckpunkte (deren Nummern von 1 bis N) so wiederherzustellen, dass das resultierende Polygon konvex ist und dieselben paarweisen Abstände aufweist. Es wird garantiert, dass die Lösung eindeutig ist. Geben Sie die Nummern der Eckpunkte in der Reihenfolge des Durchlaufs im Uhrzeigersinn aus, beginnend mit dem Eckpunkt mit der kleinsten Nummer.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (3 ≤ N ≤ 100). Die folgenden N Zeilen enthalten jeweils N ganze Zahlen — die Abstandsmatrix A, wobei A[i][j] = A[j][i] das Quadrat des euklidischen Abstands zwischen dem i-ten und j-ten Eckpunkt ist (0 ≤ A[i][j] ≤ 10^9). Die Diagonalelemente sind gleich 0. Die Matrix ist symmetrisch.

Ausgabeformat

Geben Sie N Zahlen aus — die Nummern der Eckpunkte in der Reihenfolge des Durchlaufs im Uhrzeigersinn, beginnend mit der kleinsten Nummer. Wenn die Rekonstruktion des Polygons unmöglich ist, geben Sie -1 aus.

Beispiele

Beispiel 1

EINGABE

AUSGABE

1 2 3 4

Beispiel 2

EINGABE

AUSGABE

1 2 3 4 5

Beispiel 3

EINGABE

AUSGABE

main.py