La nuit dernière, je t’ai vu courir

Dans les vastes champs de la grâce

Tu n’étais plus brisé ni dans la douleur.[1]

Vous avez trouvé une immense étendue de champs à perte de vue. Dans ces champs, vous oubliez votre passé de souffrance et de blessures. Vous courez comme un enfant dans la grâce de Dieu.

Cependant, vous découvrez un problème : ces champs contiennent plusieurs ravins. Vous risquez à tout moment d’y tomber. Pour continuer à courir librement, vous décidez de les entourer de clôtures.

Nous pouvons négliger la largeur des ravins et représenter chacun par un segment. Ces segments peuvent se croiser, tandis que vos clôtures doivent être une ou plusieurs courbes fermées, sans auto-intersection et deux à deux disjointes, de sorte que chaque ravin soit entièrement contenu dans la région fermée délimitée par l’une de ces courbes.

Bien entendu, les clôtures consomment des ressources, en quantité proportionnelle à leur longueur. Vous souhaitez minimiser la quantité totale de ressources consommées, et donc déterminer l’infimum de la longueur totale des clôtures. Autrement dit, vous cherchez le plus grand réel $x$ tel qu’aucune solution n’ait une longueur totale de clôtures strictement inférieure à $x$.

[1] Les paroles figurant dans l’énoncé proviennent de Open Fields of Grace, interprété par Jackie Evancho et composé par Lisa Venkatrathnam et Paul Sumares.

Entrée

Les données sont lues dans le fichier fields.in.

La première ligne du fichier d’entrée contient un entier $n$, le nombre de ravins.

Les $n$ lignes suivantes contiennent chacune quatre entiers $a_i,b_i,c_i,d_i$ : la $i$-ième décrit le $i$-ième ravin, représenté par le segment reliant $(a_i,b_i)$ à $(c_i,d_i)$. Les deux extrémités sont garanties distinctes, et deux segments différents ne partagent aucun point d’extrémité. Il est garanti qu’aucun triplet de points n’est aligné.

Sortie

Écrivez la sortie dans le fichier fields.out.

Affichez sur une ligne un réel représentant l’infimum de la longueur totale des clôtures. Le minimum de l’erreur absolue et de l’erreur relative entre votre réponse et la réponse de référence ne doit pas dépasser $10^{-6}$.

Exemples

Entrée 1

1
0 0 0 1

Sortie 1

2.00000000

Remarque

Un rectangle dont les quatre sommets sont $(-0.01,-0.01)$, $(-0.01,1.01)$, $(0.01,1.01)$ et $(0.01,-0.01)$ contient entièrement le segment d’entrée et a une longueur totale de $2.08$, légèrement supérieure à l’infimum.

On peut prouver qu’aucune solution n’a une longueur exactement égale à $2$. En « resserrant » indéfiniment le carré vers le segment d’entrée, on peut construire une solution de n’importe quelle longueur strictement supérieure à $2$.

Entrée 2

4
-1 7 0 7
0 0 0 1
2 -3 5 5
2 2 6 -1

Sortie 2

23.563573998194637061425470524757

Remarque

La figure ci-dessous représente les segments d’entrée. Remarquez qu’ils peuvent se croiser :

Figure 1 : explication de l’exemple 2

En nous approchant indéfiniment de ces courbes rouges, nous pouvons construire une solution de n’importe quelle longueur totale strictement supérieure à la réponse. Grâce à l’exemple 1, on voit facilement que le segment rouge en haut à gauche est compté deux fois.

Entrée 3

4
-1 1 -1 3
0 4 2 4
3 1 3 3
0 0 2 0

Sortie 3

13.656854249492380195206754896839

Remarque

La réponse est $8+4\sqrt{2}$.

L’explication est illustrée ci-dessous :

Figure 2 : explication de l’exemple 3

En nous approchant indéfiniment de ces courbes rouges, nous pouvons construire une solution de n’importe quelle longueur totale strictement supérieure à $8+4\sqrt{2}$.

Exemple 4

Voir fields/fields4.in et fields/fields4.ans dans le répertoire des participants.

Contraintes

Pour 5 % des données, $1\le n\le 1$.

Pour 10 % des données, $1\le n\le 2$.

Pour 15 % des données, $1\le n\le 10$.

Pour 30 % des données, $1\le n\le 15$.

Pour 45 % des données, $1\le n\le 30$.

Pour 55 % des données, $1\le n\le 60$.

Pour 65 % des données, $1\le n\le 120$.

Pour 75 % des données, $1\le n\le 200$.

Pour 10 % supplémentaires des données, il est garanti que la réponse comporte au plus deux courbes.

Pour 100 % des données, $1\le n\le 250$ et $0\le |a_i|,|b_i|,|c_i|,|d_i|\le 10^9$. Les deux extrémités de chaque segment sont distinctes, et deux segments différents ne partagent aucun point d’extrémité. Aucun triplet de points n’est aligné.