Через какое максимальное количество городов будет проходить железная дорога

В некотором царстве, в некотором государстве издревле повелось строить дороги, идущие с севера на юг или с запада на восток и отстоящие друг от друга на равном расстоянии. Прошли века, и вся страна покрылась равномерной транспортной сеткой, а в узлах этой сетки возникли города. Все горизонтальные дороги пронумерованы по порядку целыми числами. Аналогично пронумерованы и вертикальные дороги. Таким образом, каждый город однозначно идентифицируется номерами дорог, на пересечении которых он стоит.

Но вот пришел к власти король-реформатор, которому очень не нравилось ездить по этим дорогам. Он решил усовершенствовать дорожную сеть, добавив к ней скоростную железнодорожную ветку. Поскольку скорость движения поездов по ней очень высока, железнодорожные пути должны идти строго по прямой. Король решил соединить новым видом транспорта пару областных центров, причем так, чтобы дорога проходила через наибольшее количество других городов. Но областных центров оказалось слишком много, чтобы выполнить работу вручную. Помогите королю, написав программу, которая определит, через какое максимальное количество городов может проходить железная дорога.
Формат входных данных:

В первой строке входного файла задано целое число N (2 ≤ N ≤ 104) — количество областных центров. В каждой из последующих N строк записано по два числа — номер горизонтальной и вертикальной дорог соответственно, на пересечении которых находится областной центр. Каждый номер по абсолютной величине не превосходит 104.
Формат выходных данных:

В выходной файл выведите, через какое максимальное количество городов будет проходить железная дорога.

0

	Комментарий модератора
	! Еще одно подобное название темы и мы с Вами простимся на некоторое время.

0