Де вони?
Обмеження: 2 сек., 256 МіБ
Якось Зеник з Марічкою захотіли піти пластунським маршрутом. Пластунський маршрут є набором з nn контрольних точок, між якими потрібно йти по прямих лініях в порядку зростання номерів точок. Маршрут є замкнутим і з точки n потрібно переходити в точку 1.
Зеник знайшов в інтернеті мапу цього маршруту з пронумерованими всіма контрольними точками на ньому. Прибувши на місце, Зеник разом з Марічкою зрозуміли, що їм буде непросто. Декілька годин походивши, Марічка з Зеником заблукали. Та їм пощастило — вони вийшли до однієї з контрольних точок, біля якої була намальована мапа маршруту.
На цій мапі був зображений той самий маршрут, що й на мапі Зеника. Точки були позначені в тому ж порядку. Але було декілька відмінностей. Мапа на контрольній точці була повернутою на якийсь кут і нумерація контрольних точок на ній починалася з точки, в яку щойно прийшли Зеник з Марічкою.
Допоможіть Зенику визначити, який номер на його мапі має контрольна точка, в яку вони щойно прийшли.
Вхідні дані
У першому рядку задано одне ціле число n — кількість контрольних точок в маршруті.
У другому рядку задано 2⋅n цілих чисел. x1,y1,x2,y2 і так далі ... — координати контрольних точок на мапі Зеника.
У третьому рядку у такому ж форматі задано числа mxi,myi — координати точок на мапі з контрольної точки.
Гарантується, що маршрути на мапі Зеника та на мапі з контрольної точки збігаються. Також контрольні точки на мапах пронумеровані в однаковому напрямку.
Вихідні дані
У єдиному рядку виведіть одне ціле число — номер, яким на мапі Зеника позначена контрольна точка, в якій зараз перебувають Зеник та Марічка.
Якщо таких декілька — виведіть найменший.
Обмеження
−105≤xi,yi,mxi,myi≤105.
40% тестів:
3≤n≤1000,
сторони маршруту паралельні осям координат,
мапа на контрольній точці повернута на кут кратний 90∘.
60% тестів:
3≤n≤105,
сторони маршруту довільні,
мапа на контрольній точці повернута на довільний кут.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
6 2 -6 -4 -6 -4 -2 4 -2 4 4 2 4 3 -4 3 4 -3 4 -3 2 7 2 7 -4 | 3 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
6 1 4 5 7 5 2 -3 -4 -3 -9 1 -6 5 1 -5 1 -8 -3 -3 -3 3 5 8 5 | 3 |
Примітки
У першому тесті мапа на контрольній точці була повернута на 270∘ за годинниковою стрілкою відносно мапи Зеника. Точка з номером 1 на мапі з контрольної точки відповідає точці з номером 3 на мапі Зеника.
У другому тесті мапа на контрольній точці була повернута на 36.87∘ за годинниковою стрілкою. Точка з номером 1 на мапі з контрольної точки відповідає точці з номером 3 на мапі Зеника.