Discussion:

We all are known to the term slope of a line. It is defined as the change in the y coordinates with respect to the change in the x coordinates of a line. Any amount of changes in y coordinate with respect to x coordinate will make the same slope for a line. That means any two positions (points) that are lying on a straight line will make the same slope.

Suppose, AA and BB are two points. These two points can make a straight line. Now, another point CC will also lie on that line if the slope of AA and CC becomes equal to the slope of BB and CC. That means, AA, BB and CC will be on same line if slope(A,B)=slope(B,C)=slope(C,A)slope(A,B) = slope(B,C) = slope(C,A).

Using these rules, we can solve this problem. We have to find KK points that make the same slope as each other. The formula to find slope is:

slope,m=Δy/Δxslope, m = Δy/Δx

Here, ΔyΔy is the change in y-coordinates and ΔxΔx is the change in x-coordinates.

Steps to the solution:

  1. We will go through the first to last points.

  2. We will take one point.

  3. Calculate the slopes it (the point we took) makes with other N1N-1 points. (We must have to keep track of which points are making which slope (because we have to print the points later).

  4. The previous step will give us some slopes. From there, we will identify KK slopes that are equal or the same.

  5. If we found exactly KK slopes from the previous step, we can print the points that make this specific slope and end the program. Otherwise, we will take another point and will repeat steps 3 to 5.

Complexity for this solution:

We will calculate N1N-1 slopes for each point. Thus, NN points will take N(N1)N * (N - 1) calculations for worst cases. So we can say the complexity is O(N2)O(N^2).

Statistics

54% Solution Ratio
s_semicolonEarliest, Dec '21
steinumFastest, 0.0s
s_semicolonLightest, 524 kB
steinumShortest, 1060B
Toph uses cookies. By continuing you agree to our Cookie Policy.