Найти минимальную ширину колеи
Добрый день! Ну помогите пожалуйста с задачей!
Задан план расположения рельсов на территории железнодорожного депо. Для простоты будем считать, что территория представляет собой бесконечную плоскость, а каждый рельс представлен в виде прямой. Необходимо найти минимальную ширину колеи d, при которой рельсы можно разбить на пары так, что в каждой паре они параллельны и расстояние между ними равно d.
Формат входных данных
Первая строка содержит целое число n (1 ≤ n ≤ 2000). Каждая из последующих 2n строк содержит по четыре целых числа xi, 1, yi, 1, xi, 2, yi, 2 — координаты двух различных точек, через которые проходит рельс. Все координаты не превосходят 1000 по абсолютной величине. Прямые, соответствующие различным рельсам, не совпадают.
Формат выходных данных
Выведите вещественное число — минимальную возможную ширину колеи. Она должна быть определена с точностью не хуже 10-6.
Если ни при одной ширине колеи разбить рельсы на пары с выполнением требований задачи невозможно, выведите число −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
Выходные данные
1
Задан план расположения рельсов на территории железнодорожного депо. Для простоты будем считать, что территория представляет собой бесконечную плоскость, а каждый рельс представлен в виде прямой. Необходимо найти минимальную ширину колеи d, при которой рельсы можно разбить на пары так, что в каждой паре они параллельны и расстояние между ними равно d.
Формат входных данных
Первая строка содержит целое число n (1 ≤ n ≤ 2000). Каждая из последующих 2n строк содержит по четыре целых числа xi, 1, yi, 1, xi, 2, yi, 2 — координаты двух различных точек, через которые проходит рельс. Все координаты не превосходят 1000 по абсолютной величине. Прямые, соответствующие различным рельсам, не совпадают.
Формат выходных данных
Выведите вещественное число — минимальную возможную ширину колеи. Она должна быть определена с точностью не хуже 10-6.
Если ни при одной ширине колеи разбить рельсы на пары с выполнением требований задачи невозможно, выведите число −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
Выходные данные
1