Problem B
Balloon Darts
The balloons are modelled as points in the plane with fixed locations. For each dart you choose from where and in which direction to throw it. The dart travels in a straight line, popping all balloons in its way.
As you practised a lot during the last years, you can throw a dart precisely in any direction and it will fly infinitely far. Thus, if anyone can pop all the balloons, it is you. However, before the fun begins, you first need to determine if you can pop all balloons using at most three darts.
Input
The input consists of:
-
One line containing an integer $n$ ($1 \leq n \leq 10^4$), the number of balloons.
-
$n$ lines, each containing two integers $x$ and $y$ ($|x|, |y| \leq 10^9$), the coordinates of a balloon.
It is guaranteed that no two balloons are at the same location.
Output
Output “possible” if three darts are sufficient to pop all balloons and “impossible” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 0 0 1 1 2 4 3 9 4 16 5 25 |
possible |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 0 0 1 1 2 4 3 9 4 16 5 25 6 36 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 -1 -1 0 0 1 1 2 4 3 9 4 16 5 25 |
possible |
