Минимальное количество прямых для соединения всех заданных точек

Опубликовано: 19 Сентября, 2022

Дан 2d целочисленный массив arr[][] , содержащий N координат каждой из типов {X, Y} , задача состоит в том, чтобы найти минимальное количество прямых, необходимых для соединения всех точек массива.

Примеры:

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

Подход: Задача может быть решена на основе следующей геометрической идеи:

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

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Сначала отсортируйте массив на основе значения координаты X.
  • Пройдите массив от i = 0 до N-2 :
    • Если приведенное выше условие наклона1 = наклон2 выполняется, продолжайте без увеличения количества строк.
    • В противном случае увеличьте количество требуемых прямых линий.
  • Верните окончательное количество прямых линий в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * logN)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ