Finding a Line
Time limit4sMemory limit256 MB
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 distinct points. Decide whether some line passes through at least percent of them. In other words, decide whether a line passes through at least points.
Input
The first line has the number of points ().
The second line has the percentage as an integer ().
Each of the next lines has the coordinates and of one point as two integers separated by a space ().
All given points are distinct.
Output
Print possible if such a line exists, and impossible otherwise.
Hint
In the first example the line through , and works. It passes through 3 points, which meets the requirement of 2.75.