Annabel and Richard like to invent new games and play against each other. One day Annabel has a new game for Richard. In this game there is a game master and a player. The game master draws points on a piece of paper. The task for the player is to find a straight line, such that at least percent of the points lie exactly on that line. Richard and Annabel have very good tools for measurement and drawing. Therefore they can check whether a point lies exactly on a line or not. If the player can find such a line then the player wins. Otherwise the game master wins the game.
There is just one problem. The game master can draw the points in a way such that it is not possible at all to draw a suitable line. They need an independent mechanism to check whether there even exists a line containing at least percent of the points, i.e., points. Now it is up to you to help them and write a program to solve this task.
The input consists of:
one line with one integer (), the number of points the game master has drawn;
one line with one integer (), the percentage of points which need to lie on the line;
n lines each with two integers and (), the coordinates of a point.
No two points will coincide.
Output one line containing either "possible" if it is possible to find a suitable line or "impossible" otherwise.
Input | Output |
---|---|
5 55 0 0 10 10 10 0 0 10 3 3 | possible |
A line with (at least) 3 of the points exists. |
Input | Output |
---|---|
5 45 0 0 10 10 10 0 0 10 3 4 | impossible |
No line with at least 3 points exists. |
This NWERC 2014 problem is licensed under the CC BY-SA 3.0 license.
You can find the original problem on the NWERC website.