Motel
High-speed straight highways traverse the plain. Your task is to develop a program that determines the optimal location for a motel, minimizing the total distance to all highways.
Input
The first line contains the number of highways, n (2 ≤ n ≤ 10), each represented as a distinct straight line. For each highway j (where 1 ≤ j ≤ n), the (j + 1)-th line provides 4 natural numbers, representing the Cartesian coordinates of two distinct points on the j-th line. The distance between these points is a natural number. The numbers are given in the following order: the x and y coordinates of the first point, followed by the x and y coordinates of the second point. All coordinates are no greater than 123.
Output
The output should begin with the smallest possible sum of distances from the motel to the highways. The subsequent lines should be formatted as follows:
1. If the optimal location is a single point:
The second line should contain the number 1.
The third line should provide the coordinates of this point.
2. If the optimal location is a line segment:
The second line should contain the number 2.
The third line should provide the coordinates of one endpoint of the segment.
The fourth line should provide the coordinates of the other endpoint.
3. If the optimal location is a convex n-gon:
The second line should contain the number n.
Lines from the third to the (n + 2)-th should provide the coordinates of the vertices of this polygon (two coordinates per vertex per line).
4. If the optimal location is one of the given lines:
The second line should contain the number –1.
The third line should provide the integer coefficients of the equation of this line.
5. If the optimal location is the region between two of the given lines:
The second line should contain the number –2.
The third line should provide the integer coefficients of the equation of one line.
The fourth line should provide the integer coefficients of the equation of the other line.
Number the given lines according to the order in which their point coordinates are presented in the input. In cases 2–3, data on vertices that are intersection points of a pair of given lines should be arranged in non-decreasing order of the smaller line number, and in the case of equal smaller numbers, in increasing order of the larger number. In case 5, arrange the coefficients of the line equations in increasing order of the line number.
In cases 1–3, record the coordinates of the point in the following order:
Abscissa x.
Ordinate y.
In cases 4–5, record the coefficients of the line equation in the following order:
Coefficient of the abscissa x.
Coefficient of the ordinate y.
Constant term.
All coefficients must be integers and the smallest in absolute value, meaning the greatest common divisor of the coefficients of a line equation must be 1. Additionally, the coefficient of the abscissa must be non-negative. If it is zero, then the coefficient of the ordinate must be positive.
Any number in the answer should be presented as an irreducible fraction with an integer numerator and a natural denominator, separated by a division sign /. If the denominator is 1, omit the division sign and the denominator.