Line Through K Points

You are given N points on a 2D plane and an integer K. Your task is to determine whether there exists a straight line that passes through at least K of these points. A line in the plane can be represented in its normalized form as \[ Ax + By = C, \] where the coefficients \(A\), \(B\), and \(C\) are integers and are normalized (i.e. divided by their greatest common divisor and adjusted for a consistent sign) so that two equal lines are represented identically.

Using concepts from geometry and number theory (via the greatest common divisor), design an algorithm to decide if such a line exists. If K equals 1, the answer is trivially true, as a single point always lies on some line.

inputFormat

The input is provided via stdin and has the following format:

N K
x1 y1
x2 y2
...
xN yN

Here, N and K are integers where N is the number of points. Each of the following N lines contains two integers representing the coordinates of a point in the 2D plane.

outputFormat

Output via stdout a single line containing either True or False (without quotes). Output True if there exists at least one straight line that passes through at least K of the given points; otherwise, output False.

5 3
1 1
2 2
3 3
1 2
2 3

True