Problem
Il Ministero dell'Autotrasporto ha deciso di costruirsi un nuovo ufficio. Poiché il ministro esce regolarmente per ispezionare le vie più importanti, si è deciso che l'ufficio del ministero non dovesse trovarsi troppo lontano da esse.
Gli allineamenti più importanti sono le linee rette sul piano. Il Ministero vuole scegliere una posizione per il suo ufficio in modo che la distanza massima dall'ufficio alle autostrade sia la più breve possibile.
Devi scrivere un programma che, data l'ubicazione delle autostrade più importanti, determini l'ubicazione ottimale della casa per l'ufficio del Ministero dell'Autotrasporto.
Input
La prima riga del file di input contiene un singolo numero intero n — numero delle tracce più importanti (1 ≤ n ≤ 104 ).
Le prossime n righe descrivono le tracce. Ogni traccia è descritta da quattro numeri interi x1, y1, x2 e y2 ed è una linea retta retta passante per i punti (x1, y1) e (x2, y2) . Le coordinate dei punti dati non superano 104 in valore assoluto. Punti (x1 , y1) e (x2 , y2) non corrispondono a nessuna riga.
Uscita
Il file di output dovrebbe contenere due numeri reali separati da spazio: le coordinate del punto in cui dovrebbe essere costruito l'ufficio del Ministero dell'Autotrasporto. Le coordinate del modulo non devono superare 109, è garantito che esiste almeno una di queste risposte. Se ci sono diverse risposte ottimali, stampane qualcuna.
La risposta deve contenere un errore assoluto o relativo non superiore a 10−6, il che significa quanto segue. Lascia che la distanza massima dal punto disegnato a qualche traccia sia uguale a xe nella risposta corretta è uguale a y. La risposta verrà conteggiata se il valore dell'espressione | x .meno; e | / max(1, |y| ) non supera 10−6.
| Input |
Uscita |
|
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 |
Olimpiadi personali, Olimpiadi panrusse per scolari, Fase regionale, 2011, 2a giornata, Problema D