Рубрики

Минимальные линии, чтобы покрыть все точки

Учитывая N точек в 2-мерном пространстве, нам нужно вывести счет минимального количества линий, которые проходят через все эти N точек и которые также проходят через определенную (xO, yO) точку.

Примеры:

If given points are (-1, 3), (4, 3), (2, 1), (-1, -2), 
(3, -3) and (xO, yO) point is (1, 0) i.e. every line
must go through this point. 
Then we have to draw at least two lines to cover all
these points going through (xO, yO) as shown in below
diagram.

Мы можем решить эту проблему, рассматривая наклон всех точек с (xO, yO). Если две разные точки имеют одинаковый наклон с (xO, yO), то они могут быть покрыты одной и той же линией, поэтому мы можем отслеживать наклон каждой точки, и всякий раз, когда мы получаем новый наклон, мы увеличиваем количество линий на единицу.
В приведенном ниже коде наклон сохраняется в виде пары целых чисел, чтобы избавиться от проблемы точности, а набор используется для отслеживания возникших наклонов.
Пожалуйста, смотрите код ниже для лучшего понимания.

// C ++ программа для получения минимального количества строк для покрытия
// все точки
#include <bits/stdc++.h>

using namespace std;

  
// Служебный метод для получения gcd a и b

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b);

}

  
// метод возвращает уменьшенную форму dy / dx в паре

pair<int, int> getReducedForm(int dy, int dx)

{

    int g = gcd(abs(dy), abs(dx));

  

    // получить знак результата

    bool sign = (dy < 0) ^ (dx < 0);

  

    if (sign)

        return make_pair(-abs(dy) / g, abs(dx) / g);

    else

        return make_pair(abs(dy) / g, abs(dx) / g);

}

  
/ * метод возвращает минимальное количество строк в

    покрыть все точки, где идут все линии

    через (xO, yO) * /

int minLinesToCoverPoints(int points[][2], int N,

                                   int xO, int yO)

{

    // установить для сохранения уклона в паре

    set< pair<int, int> > st;

    pair<int, int> temp;

    int minLines = 0;

  

    // перебрать все точки один раз

    for (int i = 0; i < N; i++)

    {

        // получить координаты x и y текущей точки

        int curX = points[i][0];

        int curY = points[i][1];

  

        temp = getReducedForm(curY - yO, curX - xO);

  

        // если этого наклона нет в наборе,

        // увеличить ответ на 1 и вставить в набор

        if (st.find(temp) == st.end())

        {

            st.insert(temp);

            minLines++;

        }

    }

  

    return minLines;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int xO, yO;

    xO = 1;

    yO = 0;

  

    int points[][2] =

    {

        {-1, 3},

        {4, 3},

        {2, 1},

        {-1, -2},

        {3, -3}

    };

  

    int N = sizeof(points) / sizeof(points[0]);

    cout << minLinesToCoverPoints(points, N, xO, yO);

    return 0;

}

Выход:

2

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальные линии, чтобы покрыть все точки

0.00 (0%) 0 votes