Рейки#2499

Рейки

2 секунди

256 мегабайтів

Середня

Важливим параметром залізниці є ширина колії — відстань між двома рейками, по яких рухається поїзд. Цей параметр визначає типи поїздів і машин, які можуть працювати на залізниці.

Нещодавно космічна експедиція на планету RCC-0805 виявила на цій планеті залізничні колії. Було навіть знайдено залізничне депо, але ширину колії поки не встановлено. Проблема полягає в тому, що колії на цій планеті укладались без шпал, тому не завжди легко визначити, які рейки відповідають одна одній.

Вам дано план розташування рейок у залізничному депо. Для спрощення вважаємо, що область — це нескінченна площина, а кожна рейка подається у вигляді прямої. Вам потрібно знайти мінімальну можливу ширину колії $d$ таку, щоб рейки можна було розбити на пари так, щоб у кожній парі були паралельні рейки на відстані $d$ одна від одної.

Вхідні дані

У першому рядку задано ціле число $n$ ( $1 \leq n \leq 2000$ 1 \leq n \leq 2000). Кожен із наступних $2 n$ рядків містить чотири цілі числа $x_{i, 1}$ x_{i, 1}, $y_{i, 1}$ y_{i, 1}, $x_{i, 2}$ x_{i, 2}, $y_{i, 2}$ y_{i, 2} — координати двох різних точок, через які проходить рейка. Всі координати не перевищують $1000$ за модулем. Прямі, які відповідають різним рейкам, не збігаються.

Вихідні дані

Виведіть дійсне число — мінімальну можливу ширину колії. Її слід визначити з точністю не менш ніж $1 0^{- 6}$ 10^{-6}.

Якщо неможливо розбити рейки в пари при будь-якій ширині колії, виведіть число $- 1$ .

Приклади

Приклад 1