Problem
El Ministerio de Transporte por Carretera ha decidido construir una nueva oficina para sí mismo. Dado que el ministro sale regularmente a inspeccionar las rutas más importantes, se decidió que la oficina del ministerio no debería ubicarse demasiado lejos de ellas.
Las alineaciones más importantes son líneas rectas en el plano. El Ministerio quiere elegir una ubicación para su oficina de modo que la distancia máxima de la oficina a las carreteras sea lo más corta posible.
Debe escribir un programa que, dada la ubicación de las carreteras más importantes, determine la ubicación óptima de la casa para la oficina del Ministerio de Transporte por Carretera.
Entrada
La primera línea del archivo de entrada contiene un único entero n — número de trazas más importantes (1 ≤ n ≤ 104 ).
Las siguientes n líneas describen los rastros. Cada trazo se describe mediante cuatro números enteros x1, y1, x2 e y2 y es una recta recta que pasa por los puntos (x1, y1) y (x2, y2) . Las coordenadas de los puntos dados no exceden 104 en valor absoluto. Puntos (x1 , y1) y (x2 , y2) no coinciden con ninguna línea.
Salida
El archivo de salida debe contener dos números reales separados por espacios: las coordenadas del punto donde se debe construir la oficina del Ministerio de Transporte por Carretera. Las coordenadas del módulo no deben exceder 109, se garantiza que existe al menos una de esas respuestas. Si hay varias respuestas óptimas, imprima cualquiera de ellas.
La respuesta debe tener un error absoluto o relativo de no más de 10−6, lo que significa lo siguiente. Sea la distancia máxima desde el punto dibujado hasta alguna traza igual a x, y en la respuesta correcta es igual a y. La respuesta se contará si el valor de la expresión | x .menos; y | / máx(1, |y| ) no excede 10−6.
| Entrada |
Salida |
|
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 |
Olimpiada personal, Olimpiada de toda Rusia para escolares, Etapa regional, 2011, 2° día, Problema D