Task.
Write a program that recognizes a line pattern in a given set of points. Computer vision involves analyzing patterns in images and reconstructing the real-world objects that created them. This process is divided into two parts: detection and pattern recognition. The detection function involves selecting important features of the image, while recognition involves detecting patterns. We will consider only a small part of the problem, which includes points and lines.



Problem.
Given a set of N different points on the plane, draw every (maximum) line segment connecting a subset of 4 or more points.

You have the file point_example.py. This file contains an example of the Point class that can draw itself thanks to the matplotlib library.
point_example.py:
import matplotlib.pyplot as plt


class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def draw(self):
        plt.plot(self.x, self.y, “ro-”)

    def draw_to(self, point):
        plt.plot([self.x, point.x], [self.y, point.y], “ro-”)

    def slope_to(self, that):
        # slope between this point and that point
        pass

    def __lt__(self, other):
        # is this point lexicographically smaller than that point?
        pass

    def __eq__(self, other):
        # if not isinstance(other, Point):
            # do not attempt to compare against unrelated types
            return NotImplemented

        return self.x == other.x and self.y == other.y



if __name__ == “__main__”:
    lines = [
        [Point(14000, 10000), Point(18000, 10000)],
        [Point(18000, 10000), Point(19000, 10000)],
        [Point(19000, 10000), Point(21000, 10000)]
    ]
    points = [Point(2, 5), Point(3, 1)]

    for x, y in lines:
        x.draw()
        y.draw()
        x.draw_to(y)

    for p in points:
        p.draw()

    plt.show()


You have to implement the methods:

slope_to() returns the gradient between this point (x0,y0) and that point (x1,y1), calculated using the formula (y1-y0)/(x1-x0). Count the slope angle, which is a horizontal line as positive 0, the vertical line as positive infinity, and the degenerate segment (between the point and itself) as negative infinity.
__lt__() should compare points by their y-coordinates. The point (x0,y0) is smaller than the point (x1,y1) if and only if y0<y1 or y0=y1 and x0<x1.
You will also need a separate comparator to compare the points by the gradients they generate with the called point (x0,y0). Formally, the point (x1,y1) is smaller than the point (x2,y2) if and only if the slope (y1-y0)/(x1-x0) is less than the slope (y2-y0)/(x2-x0).
Problem 1. Brute force
Write a Brute program that examines 4 points at a time and checks whether they all lie in the same line segment, prints each such line and draws it.

To check that the 4 points p,q,r,s are collinear, check the gradient between p and q, p and r, p and s. The worst-case running time should be N4 and use space proportional to N.

Problem 2. Fast
This problem can be solved much faster. For a point p, the following method determines whether it is part of a set of 4 or more points on the same line.

Think of p as the main point.
For each other point q, determine the slope to p.
Sort the points by the slope, what they do with p
Check if there are 3 (or more) neighboring points in the ordered set that have the same slope to p.
If so, these points are collinear with p.
Applying this method to each of the N points, in turn, gives an efficient algorithm.
Write a Fast program that implements this algorithm. The worst-case running time should be N2logN and use space proportional to N.

Input.
The format of data input. Data is read from the input file in the following format. An integer N followed by N pairs of integers x y.

6

19000 10000

18000 10000

32000 10000

21000 10000

1234 5678

14000 10000

The format of the data output.
In addition to drawing lines, you must print the found lines to the console

(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000)

(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (32000, 10000)

(14000, 10000) -> (18000, 10000) -> (21000, 10000) -> (32000, 10000)

(14000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)

(18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)