Minimal variety of Straight Strains to attach all of the given Factors

Given second integer array arr[][] containing N coordinates every of kind {X, Y}, the duty is to seek out the minimal variety of straight traces required to attach all of the factors of the array.

Examples:

Enter: arr[][] = {{1, 7}, {2, 6}, {3, 5}, {4, 4}, {5, 4}, {6, 3}, {7, 2}, {8, 1}}
Output: 3
Rationalization: The diagram represents the enter factors and the minimal straight traces required.
The next 3 traces could be drawn to signify the road chart:
=> Line 1 (in pink) from (1, 7) to (4, 4) passing by means of (1, 7), (2, 6), (3, 5), and (4, 4).
=> Line 2 (in blue) from (4, 4) to (5, 4).
=> Line 3 (in inexperienced) from (5, 4) to (8, 1) passing by means of (5, 4), (6, 3), (7, 2), and (8, 1).
It may be proven that it isn’t potential to signify the road chart utilizing lower than 3 traces.

Minimal traces to attach the factors of the instance

Enter: arr[][] = {{3, 4}, {1, 2}, {7, 8}, {2, 3}}
Output: 1
Rationalization: A single line passing by means of all of the factors is sufficient to join them

Method: The issue could be solved primarily based on the next geometrical concept:

If the factors are sorted in response to their X axis worth then to calculate the variety of traces verify for 3 consecutive factors. 
If the slope of traces fashioned by first two factors and the final two factors are identical then they are often linked by a single line.
In any other case, we are going to want two totally different traces.

To calculate the slope we are going to use the formulae: 
    => slope 1 = (y2 – y1) / (x2 – x1)
    => slope 2 = (y3 – y2) / (x3 – x2)

If slope1 = slope2
(y2 – y1) / (x2 – x1) = (y3 – y2) / (x3 – x2)
(y3 – y2) * (x2 – x1) = (y2 – y1) * (x3 – x2).

Strains fashioned by consecutive 3 factors

Observe the steps talked about under to implement the concept:

• Firstly kind the array primarily based on the worth of the X coordinate.
• Traverse the array from i = 0 to N-2:
  • If the above situation of slope1 = slope2 is happy then proceed with out incrementing the rely of traces.
  • In any other case, increment the rely of straight traces required.
• Return the ultimate rely of straight traces as the reply. 

Under is the implementation of the above strategy:

Time complexity: O(N * logN) 
Auxiliary Area: O(1)