Letzte Nacht sah ich dich laufen
Auf den weiten Feldern der Gnade
Du warst nicht länger gebrochen oder voller Schmerz.[^1]
Du hast ein endlos weites Feld gefunden. Auf diesem Feld vergisst du deine einst gebrochene, schmerzhafte Vergangenheit. Wie ein Kind läufst du in Gottes Gnade.
Doch du bemerkst ein Problem: Auf diesem Feld gibt es mehrere Schluchten. Du läufst jederzeit Gefahr, in eine Schlucht zu stürzen. Um weiterhin frei und unbeschwert laufen zu können, beschließt du, diese Schluchten mit Zäunen einzufassen.
Wir können die Breite der Schluchten vernachlässigen und jede Schlucht als eine Strecke betrachten. Diese Strecken dürfen sich schneiden, und deine Zäune müssen eine oder mehrere geschlossene, sich nicht selbst und auch paarweise nicht schneidende Kurven bilden, sodass jede Schlucht vollständig innerhalb des abgeschlossenen Gebiets liegt, das von einer dieser geschlossenen Kurven begrenzt wird.
Natürlich verbrauchen Zäune Ressourcen, und dieser Verbrauch ist proportional zur Zaunlänge. Du möchtest den gesamten Ressourcenverbrauch minimieren und deshalb das Infimum der gesamten Zaunlänge bestimmen. Mit anderen Worten suchst du die größte reelle Zahl $x$, für die es keine Lösung mit einer gesamten Zaunlänge kleiner als $x$ gibt.
[^1]: Der Liedtext in der Aufgabenstellung stammt aus Jackie Evanchos „Open Fields of Grace“, komponiert von Lisa Venkatrathnam und Paul Sumares.
Eingabe
Lies die Daten aus der Datei fields.in.
Die erste Zeile der Eingabedatei enthält eine ganze Zahl $n$, die Anzahl der Schluchten.
Es folgen $n$ Zeilen. Die $i$-te Zeile enthält vier ganze Zahlen $a_i,b_i,c_i,d_i$. Sie beschreiben die $i$-te Schlucht als Strecke zwischen den Punkten $(a_i,b_i)$ und $(c_i,d_i)$. Die beiden Endpunkte sind garantiert verschieden, und verschiedene Strecken haben keine gemeinsamen Endpunkte. Es ist garantiert, dass keine drei Punkte auf einer Geraden liegen.
Ausgabe
Schreibe die Ausgabe in die Datei fields.out.
Gib in einer Zeile eine reelle Zahl aus: das Infimum der gesamten Zaunlänge. Das Minimum aus dem absoluten und dem relativen Fehler deiner Antwort gegenüber der korrekten Antwort darf $10^{-6}$ nicht überschreiten.
Beispiele
Eingabe 1
1 0 0 0 1
Ausgabe 1
2.00000000
Hinweis
Ein Rechteck mit den vier Eckpunkten $(-0.01,-0.01)$, $(-0.01,1.01)$, $(0.01,1.01)$ und $(0.01,-0.01)$ enthält die eingegebene Strecke vollständig und hat den Umfang $2.08$, etwas mehr als das Infimum.
Man kann beweisen, dass keine Lösung mit einer Länge von genau $2$ existiert. Indem man das Quadrat unbegrenzt eng um die eingegebene Strecke zusammenzieht, kann man eine Lösung mit jeder beliebigen Länge größer als $2$ konstruieren.
Eingabe 2
4 -1 7 0 7 0 0 0 1 2 -3 5 5 2 2 6 -1
Ausgabe 2
23.563573998194637061425470524757
Hinweis
Die folgende Abbildung zeigt die eingegebenen Strecken. Beachte, dass sich die Strecken schneiden dürfen:
Abbildung 1: Erläuterung zu Beispiel 2
Indem wir uns diesen roten Kurven unbegrenzt annähern, können wir Lösungen mit jeder beliebigen Gesamtlänge größer als die Antwort konstruieren. Aus Beispiel 1 lässt sich leicht erkennen, dass die rote Strecke oben links zweimal gezählt wird.
Eingabe 3
4 -1 1 -1 3 0 4 2 4 3 1 3 3 0 0 2 0
Ausgabe 3
13.656854249492380195206754896839
Hinweis
Die Antwort ist $8+4\sqrt{2}$.
Die Erklärung zeigt die folgende Abbildung:
Abbildung 2: Erläuterung zu Beispiel 3
Indem wir uns diesen roten Kurven unbegrenzt annähern, können wir Lösungen mit jeder beliebigen Gesamtlänge größer als $8+4\sqrt{2}$ konstruieren.
Beispiel 4
Siehe fields/fields4.in und fields/fields4.ans im Teilnehmerverzeichnis.
Beschränkungen
Für 5% der Testdaten gilt $1 \le n \le 1$.
Für 10% der Testdaten gilt $1 \le n \le 2$.
Für 15% der Testdaten gilt $1 \le n \le 10$.
Für 30% der Testdaten gilt $1 \le n \le 15$.
Für 45% der Testdaten gilt $1 \le n \le 30$.
Für 55% der Testdaten gilt $1 \le n \le 60$.
Für 65% der Testdaten gilt $1 \le n \le 120$.
Für 75% der Testdaten gilt $1 \le n \le 200$.
Für weitere 10% der Testdaten ist garantiert, dass die Antwort höchstens zwei Kurven enthält.
Für 100% der Testdaten gilt $1 \le n \le 250$ und $0 \le |a_i|,|b_i|,|c_i|,|d_i| \le 10^9$. Die beiden Endpunkte sind garantiert verschieden, und verschiedene Strecken haben keine gemeinsamen Endpunkte. Es ist garantiert, dass keine drei Punkte auf einer Geraden liegen.