409745: GYM103715 F Сократить путешествие

F. Сократить путешествиеограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Лера решила отправиться в путешествие. Она уже выбрала $$$n$$$ мест, которые она хочет посетить и определила порядок посещения мест $$$p_1, p_2, ..., p_n$$$. Каждое место задается его координатой — точкой в двумерном пространстве. Лера планировала сначала посетить место с координатой $$$p_1$$$, затем место с координатой $$$p_2$$$ и т.д. Из одного места в другое Лера будет путешествовать кратчайший маршрутом — по прямой.

После некоторых расчетов Лера поняла, что ее путешествие слишком длинное. Чтобы сократить своё путешествие, Лера готова отказаться от посещения ровно одного места. Помогите Лере и найдите номер места, которое ей стоит пропустить, чтобы её путешествие стало как можно короче. Под «длиной» путешествия понимается суммарное расстояние, которое предстоит преодолеть Лере. Для лучшего понимания условия смотрите примечание.

Входные данные

Первая строк содержит единственное целое число $$$n$$$ ($$$3 \le n \le 100000$$$) — количество мест, которая Лера хочет посетить.

Следующие $$$n$$$ строк описывают координаты мест: $$$i+1$$$-я строка входных данных содержит два целых числа $$$x$$$ и $$$y$$$ ($$$-1000 \le x, y \le 1000$$$) — координаты $$$i$$$-го места.

Выходные данные

Выведите единственное число — номер места, которое Лере стоит пропустить, чтобы суммарное пройденное расстояние было минимально возможным. Если таких мест несколько, разрешается вывести любое из них.

Формально, пусть суммарное расстояние, которое пройдет Лера, согласно вашему ответу равно $$$a$$$, а согласно ответу жюри равно $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$, то есть абсолютная или относительная ошибка между вашим ответом и ответом жюри не должна превосходить $$$10^{-9}$$$.

ПримерыВходные данные

5
0 0
3 5
3 0
8 5
7 1

Выходные данные

2

Входные данные

4
0 0
0 1
1 1
1 0

Выходные данные

1

Входные данные

3
5 5
5 5
5 5

Выходные данные

1

Примечание

В первом примере путь Леры выглядит следующим образом:

Если Лера уберет первое место из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p2, p3) + dist(p3, p4) + dist(p4, p5) = 5 + 7.07 + 4.12 = 16.19$$$.

Если Лера уберет второе место из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p1, p3) + dist(p3, p4) + dist(p4, p5) = 3 + 7.07 + 4.12 = 14.19$$$.

При исключении третьего места из маршрута получаем, что суммарное расстояние равно: $$$dist(p1, p2) + dist(p2, p4) + dist(p4, p5) = 5.83 + 5 + 4.12 = 14.95$$$.

Если пропустить четвертое места в маршруте, то суммарное расстояние равно: $$$dist(p1, p2) + dist(p2, p3) + dist(p3, p5) = 5.83 + 5 + 4.12 = 14.95$$$.

Если Лера уберет пятое места из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p1, p2) + dist(p2, p3) + dist(p3, p4) = 5.83 + 5 + 7.07 = 17.9$$$.

Таким образом, чтобы путешествие Леры стало как можно короче, ей следует пропустить второе место.

*$$$dist(p_i, p_j)$$$ — расстояние между точками $$$i$$$ и $$$j$$$ по прямой.

Во втором примере Лере следует пропустить $$$1$$$ или $$$4$$$ место (можно вывести как $$$1$$$, так и $$$4$$$ — оба ответа будут верными). Суммарное пройденное расстояние в таком случае равно $$$2$$$.

В третьем примере Лера собирается посетить одно и тоже место три раза, поэтому суммарное пройденное расстояние в любом случае будет $$$0$$$. Значит можно вывести любое число от $$$1$$$ до $$$3$$$.