Problem
Le ministère des Transports routiers a décidé de se construire un nouveau bureau. Étant donné que le ministre se rend régulièrement pour inspecter les routes les plus importantes, il a été décidé que le bureau du ministère ne devrait pas être situé trop loin de celles-ci.
Les alignements les plus importants sont les lignes droites sur le plan. Le ministère souhaite choisir un emplacement pour son bureau afin que la distance maximale entre le bureau et les autoroutes soit la plus courte possible.
Vous devez rédiger un programme qui, compte tenu de l'emplacement des autoroutes les plus importantes, détermine l'emplacement optimal de la maison pour le bureau du ministère des Transports routiers.
Entrée
La première ligne du fichier d'entrée contient un seul entier n — nombre de traces les plus importantes (1 ≤ n ≤ 104 ).
Les n lignes suivantes décrivent les traces. Chaque trace est décrite par quatre nombres entiers x1, y1, x2 et y2 et est une droite droite passant par les points (x1, y1) et (x2, y2) . Les coordonnées des points donnés ne dépassent pas 104 en valeur absolue. Points (x1 , y1) ; et (x2 , y2) ; ne correspondent à aucune ligne.
Sortie
Le fichier de sortie doit contenir deux nombres réels séparés par des espaces : les coordonnées du point où le bureau du ministère des Transports routiers doit être construit. Les coordonnées modulo ne doivent pas dépasser 109, il est garanti qu'au moins une telle réponse existe. S'il existe plusieurs réponses optimales, imprimez l'une d'entre elles.
La réponse doit avoir une erreur absolue ou relative ne dépassant pas 10−6, ce qui signifie ce qui suit. Supposons que la distance maximale entre le point dessiné et une trace soit égale à x, et dans la bonne réponse, elle est égale à y. La réponse sera comptée si la valeur de l'expression | x .moins ; y | / max(1, |y| ) ne dépasse pas 10−6.
| Entrée |
Sortie |
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
0.5000000004656613 0.4999999995343387 |
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
4040.9996151750674 12003.999615175067 |
Olympiade personnelle, Olympiade panrusse des écoliers, Stade régional, 2011, 2e jour, Problème D