This page is still under construction.

Parts of this page are still being built. What you see may change.

Finding a Line

Time limit4sMemory limit256 MB

Summary
Decide whether any single line passes through at least p percent of N given points.
Level

Medium6 of 10

Topics
Probability, Geometry, Hash map
Solved
No attempts yet

Problem

A coordinate plane holds NN distinct points. Decide whether some line passes through at least pp percent of them. In other words, decide whether a line passes through at least 0.01×N×p0.01 \times N \times p points.

Input

The first line has the number of points NN (1≤N≤1051 \le N \le 10^5).

The second line has the percentage pp as an integer (20≤p≤10020 \le p \le 100).

Each of the next NN lines has the coordinates xx and yy of one point as two integers separated by a space (0≤x,y≤1090 \le x, y \le 10^9).

All given points are distinct.

Output

Print possible if such a line exists, and impossible otherwise.

Hint

In the first example the line through (0,0)(0, 0), (3,3)(3, 3) and (10,10)(10, 10) works. It passes through 3 points, which meets the requirement of 2.75.

Examples4

  1. Example 1

    Input
    5
    55
    0 0
    10 10
    10 0
    0 10
    3 3
    
    Expected output
    possible
    
  2. Example 2

    Input
    5
    45
    0 0
    10 10
    10 0
    0 10
    3 4
    
    Expected output
    impossible
    
  3. Example 3

    Input
    10
    90
    4 0
    4 1
    4 2
    4 3
    4 4
    4 5
    4 6
    4 7
    4 8
    5 0
    
    Expected output
    possible
    
  4. Example 4

    Input
    7
    50
    0 0
    1 1
    2 2
    3 3
    5 0
    3 7
    8 1
    
    Expected output
    possible