Задача №1980. Волшебный лес
В волшебном лесу растут N деревьев. На плане леса они изображены точками (диаметром деревьев можно пренебречь). Территорией леса считается наименьший по площади выпуклый многоугольник (возможно, вырожденный), содержащий в себе все деревья.
Отважный путешественник и писатель Ручкин однажды решился на отчаянный поступок — он совершил путешествие в этот лес. После этого он описал свое путешествие в книге. В частности, в книге описаны все деревья леса в том порядке, в каком они встречались Ручкину (каждое дерево описано ровно один раз).
Художник Кистин решил нарисовать иллюстрацию для этой книги. Для этого он приехал и остановился в деревне недалеко от волшебного леса. Теперь он хочет выбрать точку, с которой он будет рисовать иллюстрацию. Кистин очень боится заходить в волшебный лес, поэтому хочет найти точку для рисования обязательно за пределами леса (в том числе, она не может находиться на границе леса).
Он решил нарисовать весь лес: он хочет взять длинный-длинный холст, и зарисовать весь лес справа налево, от самой правой точки леса до самой левой. При этом деревья леса должны на картине идти справа налево ровно в том же порядке, в котором они описаны в книге. Естественно, никакое дерево не должно быть заслонено другим деревом (т.е. на отрезке между Кистиным и деревом не может быть других деревьев).
Помогите ему: напишите программу, которая по координатам деревьев волшебного леса в том порядке, в каком они описаны у Ручкина, поможет Кистину выбрать точку, из которой деревья видны в требуемом порядке.
Задано число N — количество деревьев в лесу (1 ≤ N ≤ 100000). Далее перечислено N пар чисел, задающих координаты деревьев в том порядке, в каком они описаны в книге Ручкина. Все координаты – целые числа, не превосходящие по абсолютной величине 105. Гарантируется, что никакие два дерева не растут в одной точке.
Если подобрать точку для Кистина возможно, выведите сообщение Possible, а в следующей строке — два вещественных числа: координаты точки. Координаты выведенной точки не должны превышать 1015 по абсолютной величине. Если подобрать точку с указанными ограничениями не удастся, выведите сообщение Impossible.
При проверке ответа для случая Possible он будет считаться верным, если на расстоянии менее 10–5 от выведенной точки будет существовать точка, удовлетворяющая условию.
Примеры
| Входные данные | Выходные данные |
| 3 0 0 1 2 2 1 | Possible 1 4 |
| 3 1 0 2 0 3 0 | Possible 1 1 |
| 3 1 0 3 0 2 0 | Impossible |
| 4 0 0 2 3 4 2 3 1 | Impossible |
| 4 0 0 4 0 2 2 4 4 | Possible -2 2 |