eolymp
bolt
Try our new interface for solving problems
Məsələlər

Рельсы

Рельсы

Важным параметром железной дороги является ширина колеи --- расстояние между двумя рельсами, по которым едет поезд. Именно этот параметр определяет типы поездов и других машин, которые могут ездить по железной дороге. Недавно космическая экспедиция на планету RCC-0805 выяснила, что железные дороги есть и на этой планете. Было даже найдено железнодорожное депо, однако определить ширину колеи пока не удалось. Дело в том, что железные дороги на этой планете укладывались без шпал, поэтому определить, какие рельсы друг другу соответствуют не всегда просто. Задан план расположения рельсов на территории железнодорожного депо. Для простоты будем считать, что территория представляет собой бесконечную плоскость, а каждый рельс представлен в виде прямой. Необходимо найти минимальную ширину колеи \textbf{d}, при которой рельсы можно разбить на пары так, что в каждой паре они параллельны и расстояние между ними равно \textbf{d}. \InputFile Первая строка содержит целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{2000}). Каждая из последующих \textbf{2n} строк содержит по четыре целых числа \textbf{x_i}_\{, 1\}, \textbf{y_i}_\{, 1\}, \textbf{x_i}_\{, 2\}, \textbf{y_i}_\{, 2\} --- координаты двух различных точек, через которые проходит рельс. Все координаты не превосходят \textbf{1000} по абсолютной величине. Прямые, соответствующие различным рельсам, не совпадают. \OutputFile Выведите вещественное число --- минимальную возможную ширину колеи. Она должна быть определена с точностью не хуже \textbf{10^\{-6\}}. Если ни при одной ширине колеи разбить рельсы на пары с выполнением требований задачи невозможно, выведите число \textbf{−1}.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
0 0 0 1
1 0 1 1
2 0 2 1
3 0 3 1
0 0 1 0
0 1 1 1
Çıxış verilənləri #1
1.00000000000000000000
Mənbə Russian-Code-Cup-2011 1-й кв. раунд