eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Будинок біля дороги

Будинок біля дороги

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Міністерство дорожнього транспорту вирішило побудувати собі новий офіс. Оскільки міністр регулярно виїзджає з інспекцією найбільш важливих трас, було вирішено, що офіс міністерства не повинен розміщуватись занадто далеко від них.

Найбільш важливі траси являють собою прямі на площині. Міністерство хоче вибрати таке розміщення для свого офісу, щоб максимум з відстаней від офісу до трас був якомога меншим.

Потрібно написати програму, яка за заданим розміщенням найбільш важливих трас визначає оптимальне розміщення будинку для офіса міністерства дорожнього транспорту.

Вхідні дані

Перший рядок вхідного файлу містить одне ціле число n — кількість найбільш важливих трас (1n10^4).

Наступні n рядків описують траси. Кожна траса описується чотирма цілими числами x_1, y_1, x_2 та y_2 і являє собою пряму, яка проходить через точки (x_1, y_1) та (x_2, y_2). Координати заданих точок не перевищують по модулю 10^4. Точки (x_1, y_1) та (x_2, y_2) ні для якої прямої не співпадають.

Вихідні дані

Вихідний файл повинен містити два відокремлених пропуском дійсних числа: координати точки, у якій слід побудувати офіс міністерства дорожнього транспорту. Координати по модулю не повинні перевищувати 10^9, гарантується, що хоча б одна така відповідь існує. Якщо оптимальних відповідей декілька, необхідно вивести довільну з них.

Відповідь повинна мати абсолютну або відносну похибку не більше 10^{-6}, що означає наступне. Нехай максимальна відстань від виведеної точки до деякої траси рівна x, а у правильній відповіді вона рівна y. Відповідь буде зараховано, якщо значення виразу |x – y| / max{1, | y| } не перевищує 10^{-6}.

Приклад

Вхідні дані #1
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
Вихідні дані #1
0.5 0.5