Minimum number of Straight Lines to connect all the given Points

Given 2d integer array arr[][] containing N coordinates each of type {X, Y}, the task is to find the minimum number of straight lines required to connect all the points of the array.

Examples:

Input: arr[][] = {{1, 7}, {2, 6}, {3, 5}, {4, 4}, {5, 4}, {6, 3}, {7, 2}, {8, 1}}
Output: 3
Explanation: The diagram represents the input points and the minimum straight lines required.
The following 3 lines can be drawn to represent the line chart:
=> Line 1 (in red) from (1, 7) to (4, 4) passing through (1, 7), (2, 6), (3, 5), and (4, 4).
=> Line 2 (in blue) from (4, 4) to (5, 4).
=> Line 3 (in green) from (5, 4) to (8, 1) passing through (5, 4), (6, 3), (7, 2), and (8, 1).
It can be shown that it is not possible to represent the line chart using less than 3 lines.

Minimum lines to connect the points of the example

Input: arr[][] = {{3, 4}, {1, 2}, {7, 8}, {2, 3}}
Output: 1
Explanation: A single line passing through all the points is enough to connect them

Approach: The problem can be solved based on the following geometrical idea:

If the points are sorted according to their X axis value then to calculate the number of lines check for three consecutive points. 
If the slope of lines formed by first two points and the last two points are same then they can be connected by a single line.
Otherwise, we will need two different lines.

To calculate the slope we will 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).

Lines formed by consecutive 3 points

Lines formed by consecutive 3 points

Follow the steps mentioned below to implement the idea:

  • Firstly sort the array based on the value of the X coordinate.
  • Traverse the array from i = 0 to N-2:
    • If the above condition of slope1 = slope2 is satisfied then continue without incrementing the count of lines.
    • Otherwise, increment the count of straight lines required.
  • Return the final count of straight lines as the answer. 

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int minimumLines(vector<vector<int> >& arr)

{

    int n = arr.size();

  

    

    

    if (n == 1)

        return 0;

  

    

    sort(arr.begin(), arr.end());

  

    int numoflines = 1;

  

    

    

    

    

    for (int i = 2; i < n; i++) {

        int x1 = arr[i][0];

        int x2 = arr[i - 1][0];

        int x3 = arr[i - 2][0];

        int y1 = arr[i][1];

        int y2 = arr[i - 1][1];

        int y3 = arr[i - 2][1];

        int slope1 = (y3 - y2) * (x2 - x1);

        int slope2 = (y2 - y1) * (x3 - x2);

  

        if (slope1 != slope2)

            numoflines++;

    }

  

    

    return numoflines;

}

  

int main()

{

    vector<vector<int> > vect{ { 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }, { 5, 4 }, { 6, 3 }, { 7, 2 }, { 8, 1 } };

  

    

    cout << minimumLines(vect);

    return 0;

}

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

By Julio MarchiPosted on