Мотель
Равнину пересекают прямолинейные скоростные автострады. Напишите программу, которая определит оптимальное место для мотеля, минимизируя сумму расстояний до всех автострад.
Входные данные
Первая строка содержит количество автострад n (2 ≤ n ≤ 10), каждая из которых представлена как прямая линия. Для каждой автострады j (где 1 ≤ j ≤ n), следующая строка содержит 4 натуральных числа — декартовы координаты двух различных точек на j-ой прямой. Эти точки заданы в порядке: абсцисса и ордината первой точки, затем абсцисса и ордината второй точки. Все координаты не превышают 123.
Выходные данные
Первая строка должна содержать минимальную возможную сумму расстояний от мотеля до всех автострад. Далее следуют строки в зависимости от результата:
1. Если оптимальное место — одна точка:
Вторая строка содержит число 1;
Третья строка содержит координаты этой точки.
2. Если оптимальное место — отрезок:
Вторая строка содержит число 2;
Третья строка содержит координаты одного конца отрезка;
Четвертая строка содержит координаты другого конца отрезка.
3. Если оптимальное место — выпуклый n-угольник:
Вторая строка содержит число n;
Строки от третьей до (n + 2)-ой содержат координаты вершин многоугольника (по две координаты на строку).
4. Если оптимальное место — одна из данных прямых:
Вторая строка содержит число –1;
Третья строка содержит целые коэффициенты уравнения этой прямой.
5. Если оптимальное место — часть плоскости между двумя прямыми:
Вторая строка содержит число –2;
Третья строка содержит целые коэффициенты уравнения одной из прямых;
Четвертая строка содержит целые коэффициенты уравнения другой прямой.
Прямые, координаты точек которых даны во входных данных, нумеруются в порядке их появления. В случаях 2–3 данные о вершинах, являющихся точками пересечения пар прямых, должны быть упорядочены по неубыванию меньшего номера пары, а при одинаковых меньших номерах — по возрастанию большего номера. В случае 5 коэффициенты уравнений прямых должны быть упорядочены по возрастанию номера прямой.
В случаях 1–3 координаты точки записываются в порядке:
абсцисса x;
ордината y.
В случаях 4–5 коэффициенты уравнения прямой записываются в порядке:
коэффициент при абсциссе x;
коэффициент при ординате y;
свободный член.
Все коэффициенты должны быть целыми и минимальными по абсолютной величине. Наибольший общий делитель коэффициентов уравнения прямой должен равняться 1. Коэффициент при абсциссе должен быть неотрицательным. Если он равен нулю, то коэффициент при ординате должен быть положительным.
Любое число в ответе представляется несократимой дробью с целым числителем и натуральным знаменателем, разделенными знаком деления /. Если знаменатель равен 1, знак деления и знаменатель не указываются.