Идет метеоритный дождь, на небе виднеются n метеоров. Небо можно рассматривать как двухмерную Евклидову плоскость, а метеоры — как точки на этой плоскости.
Лиса Сиель смотрит в небо. Она заметила, что орбита каждого метеора — прямая, а скорость каждого метеора постоянна. Теперь Сиель хочет узнать, чему равно максимальное количество метеоритов таких, что любая пара из них когда-либо встречалась (находились в одно и то же время в одном и том же месте)? Обратите внимание, что время не ограниченно и может быть отрицательным. Считается, что метеоры никогда не сталкиваются, когда оказываются в одно и то же время в одном и том же месте.
Выходные данные
Выведите единственное целое число — максимальное количество метеоритов таких, что любая пара из них когда-либо встречалась.
Примечание
В первом примере, метеоры 1 и 2 встречаются во время t=-1 в точке (0, 0).
Во втором примере, метеоры 1 и 2 встречаются во время t=1 в точке (1, 0), метеоры 1 и 3 встречаются во время t=0 в точке (0, 0), а метеоры 2 и 3 встречаются во время t=2 в точке (0, 1).
В третьем примере никакие два метеора не встречаются
В четвертом примере есть только один метеор, его скорость равна нулю.
Если ваш браузер не поддерживает анимацию png, вы можете посмотреть gif анимацию по ссылкам:
388_E_img_1.gif
388_E_img_2.gif
388_E_img_4.gif
388_E_img_3.gif
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
0 0 1 1 0 2
0 1 0 1 2 0
|
2
|
|
2
|
3
-1 -1 0 3 3 0
0 2 -1 -1 3 -2
-2 0 -1 6 0 3
|
3
|
|
3
|
4
0 0 0 1 0 1
0 0 1 1 1 1
0 1 1 1 1 0
0 1 0 1 0 0
|
1
|
|
4
|
1
0 0 0 1 0 0
|
1
|