Problem
O Ministério dos Transportes Rodoviários decidiu construir um novo escritório para si. Como o ministro sai regularmente para inspecionar as rotas mais importantes, foi decidido que o escritório do ministério não deveria estar localizado muito longe delas.
Os alinhamentos mais importantes são linhas retas no plano. O Ministério quer escolher um local para seu escritório de modo que a distância máxima do escritório às rodovias seja a menor possível.
Você precisa escrever um programa que, dada a localização das rodovias mais importantes, determine a localização ideal da casa para o escritório do Ministério dos Transportes Rodoviários.
Entrada
A primeira linha do arquivo de entrada contém um único inteiro n — número de traços mais importantes (1 ≤ n ≤ 104 ).
As próximas n linhas descrevem os traços. Cada traço é descrito por quatro inteiros x1, y1, x2 e y2 e é uma reta linha passando pelos pontos (x1, y1) e (x2, y2). As coordenadas dos pontos dados não excedem 104 em valor absoluto. Pontos (x1 , y1) e (x2 , y2) não correspondem a nenhuma linha.
Saída
O arquivo de saída deve conter dois números reais separados por espaços: as coordenadas do ponto onde deve ser construído o escritório do Ministério dos Transportes Rodoviários. As coordenadas do módulo não devem exceder 109, é garantido que existe pelo menos uma dessas respostas. Se houver várias respostas ideais, imprima qualquer uma delas.
A resposta deve ter um erro absoluto ou relativo não superior a 10&menos;6, o que significa o seguinte. Deixe a distância máxima do ponto desenhado para algum traço ser igual a x, e na resposta correta é igual a y. A resposta será contabilizada se o valor da expressão | x .menos; y | / max(1, |y| ) não exceda 10&menos;6.
| Entrada |
Saída |
|
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 |
Olimpíada Pessoal, Olimpíada de Toda a Rússia para crianças em idade escolar, Etapa Regional, 2011, 2º dia, D