eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Поиск линий

Поиск линий

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Аннабель и Ричард любят придумывать новые игры и играть друг против друга. Однажды у Анабель появилась новая игра для Ричарда. В этой игре есть мастер и игрок. Мастер рисует n точек на листе бумаги. Задача для игрока - найти прямую линию, такую, чтобы по крайней мере p процентов точек лежало точно на этой линии. Ричард и Аннабель имеют очень хорошие инструменты для измерения и рисования. Поэтому они могут проверить, находится ли точка точно на линии или нет. Если игрок может найти такую линию, то побеждает игрок. В противном случае мастер выигрывает игру.

Есть только одна проблема. Мастер может рисовать точки таким образом, что вообще невозможно нарисовать подходящую линию. Им нужен независимый механизм для проверки, существует ли даже линия, содержащая не менее p процентов точек, то есть ceil (n * p / 100). Теперь Вы можете помочь им и написать программу для решения этой задачи.

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

Состоит из:

  • строка содержит число n (1n10^5) - количество точек, которое нарисовал мастер;

  • строка содержит целое число p (20p100) - процент точек который должен лежать на прямой;

  • n строк с двумя целыми числами x и y (0x, y10^9) - координаты точки.

Никакие две точки не совпадают.

Вывести строку "possible" если искомая прямая существует и "impossible" иначе.

prb7856.gif

Пример

Входные данные #1
5
55
0 0
10 10
10 0
0 10
3 3
Выходные данные #1
possible
Входные данные #2
5
45
0 0
10 10
10 0
0 10
3 4
Выходные данные #2
impossible
Источник 2014 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача F