На плоскости дано множество отрезков. Требуется найти прямую, которая пересекла бы наибольшее возможное количество из данных отрезков и при этом проходила бы как минимум через две точки с целочисленными координатами.
Считается, что прямая пересекает отрезок, если она имеет с ним хотя бы одну общую точку (т.е. она может проходить через конец отрезка, внутреннюю точку отрезка, либо содержать весь отрезок).
Формат входных данных
Сначала вводится число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел X
i1, Y
i1, X
i2, Y
i2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.
Заданные отрезки могут пересекаться, иметь общие части, один из них может полностью содержаться внутри другого. Отрезки имеют ненулевую длину.
Формат выходных данных
Выведите координаты каких-нибудь двух точек, через которые проходит прямая, пересекающая наибольшее количество отрезков. Координаты точек должны быть целыми и не должны по модулю превышать 10
7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0 1 0
0 1 1 1
0 2 1 2
|
0 0
1 2
|
|
2
|
2
0 0 1 0
0 0 1 0
|
0 0
1 0
|
|
3
|
2
0 0 1 0
2 0 1 0
|
0 0
1 0
|
|
4
|
5
-1 0 3 4
2 3 5 6
0 2 2 -2
8 5 9 2
8 5 9 2
|
-1 0
9 2
|