Suchen Sie anhand einer Liste mit ganzzahligen Koordinaten den Bereich des größten konvexen Polygons, das Sie aus der Liste erstellen können, so dass:
- Jeder Scheitelpunkt ist in der Liste
- Das Polygon enthält kein Element der Liste.
Beispiel:
(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)
Visualisiert:
o o
o o o
o o o
o o o
o
o o
Das größte konvexe Polygon, das Sie daraus erstellen können, ist Folgendes:
o
o o
o o
o o
o
o
Mit einer Fläche von 12.
Sie können die Koordinatenliste in jedem vernünftigen Format verwenden und sollten (entsprechend Ihrer Sprache) den Bereich des größten konvexen Polygons ausgeben, der auf mindestens zwei Nachkommastellen gerundet ist.
Außerdem müssen Sie einen Algorithmus verwenden und nicht einfach alle Teilmengen der Punkte brachial erzwingen. Um dies zu erzwingen, muss Ihr Programm auf einem modernen PC in weniger als einer Minute eine Liste von 50 Scheitelpunkten auflösen.
Kürzester Code in Bytes gewinnt.
Antworten:
Javascript ES6, 738 Bytes
Hier ist eine ES5-Version oder eine niedrigere Version, die in den meisten Browsern und Knoten ohne Optimierung funktionieren sollte: 827 Byte
Code gibt eine anonyme Funktion zurück. Als Parameter wird beispielsweise ein Array von Punkten verwendet
[[0,1],[2,3],[4,5]]
. Um es zu verwenden, können Sie esvar f=
davor platzieren oder, wenn Sie es über die Befehlszeile verwenden möchten,(process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))
an das Ende anfügen und es wie folgt aufrufennode convpol.js '(1,2)(3,4)(5,6)'
Danke für die Herausforderung! Da es keine Referenzimplementierung gibt, kann ich nicht beweisen, dass dies korrekt ist, aber es ist zumindest für Permutationen der Punktliste konsistent. Ich hätte fast nicht gedacht, dass dies funktionieren würde, da Versionen mit Debugging-Code, selbst deaktiviert, mit exponentiellem Zeitanstieg viel zu langsam waren. Ich entschied mich trotzdem, Golf zu spielen, und war erfreut zu sehen, dass es für 50 Punkte auf meiner Maschine auf unter 2 Sekunden abfiel. Es kann ungefähr 130 Punkte in 1 Minute berechnen.
Der Algorithmus ähnelt dem Graham-Scan , muss jedoch überall nach leeren konvexen Hüllen suchen.
Erläuterung
Hier ist eine allgemeine Übersicht über die Funktionsweise des Algorithmus. Bei diesem Algorithmus wird nur nach konvexen Schleifen gegen den Uhrzeigersinn gesucht, die keinen Punkt einschließen. Das Verfahren sieht ungefähr so aus:
Außerdem zeichnen wir zur Optimierung das erste Paar der Kette als markiert auf, sodass jede Suche nach dem Anzeigen dieses Paares an einer beliebigen Stelle in der Kette sofort abgebrochen werden kann, da das größte Polygon mit diesem Paar bereits gefunden wurde.
Dieser Algorithmus sollte niemals zweimal ein Polygon finden, und ich habe dies experimentell überprüft.
quelle
===
und!==
mit==
und!=
, aber ich konnte nicht sicher sein, ohne Ihren Code zu verstehen ...(x,i)=>p.i==i
(13 Zeichen) sindx=>p===x
auch nach der Optimierung viel länger als (8 Zeichen).