Рубрики

Подсчитайте максимальное количество очков на одной линии

Для данной точки N на плоскости в виде пары (x, y) координат нам нужно найти максимальное количество точек, лежащих на одной прямой.

Примеры:

Input : points[] = {-1, 1}, {0, 0}, {1, 1}, 
                    {2, 2}, {3, 3}, {3, 4} 
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}

Мы можем решить вышеуказанную проблему следующим образом: для каждой точки p рассчитайте ее наклон с другими точками и используйте карту, чтобы записать, сколько точек имеют одинаковый наклон, по которому мы можем узнать, сколько точек находятся на одной линии с p как их один пункт. Для каждой точки продолжайте делать то же самое и обновите максимальное количество найденных баллов.

Некоторые вещи, на которые следует обратить внимание при реализации:
1) если две точки (x1, y1) и (x2, y2), то их наклон будет (y2 — y1) / (x2 — x1), что может быть двойным значением и может вызвать проблемы с точностью. Чтобы избавиться от проблем точности, мы рассматриваем наклон как пару ((y2 — y1), (x2 — x1)) вместо отношения и уменьшаем пару на их gcd перед вставкой в карту. В приведенных ниже кодовых точках, которые являются вертикальными или повторяются, рассматриваются отдельно.

2) Если мы используем unordered_map в c ++ или HashMap в Java для хранения пары склона, то общая сложность решения будет равна O (n ^ 2)

/ * C / C ++ программа для поиска максимального количества точек
которые лежат на одной линии * /
#include <bits/stdc++.h>
#include <boost/functional/hash.hpp>

  

using namespace std;

  
// метод нахождения максимальной коллинеарной точки

int maxPointOnSameLine(vector< pair<int, int> > points)

{

    int N = points.size();

    if (N < 2)

        return N;

  

    int maxPoint = 0;

    int curMax, overlapPoints, verticalPoints;

  

    // здесь, так как мы используем unordered_map

    // который основан на хеш-функции

    // Но по умолчанию у нас нет хеш-функции для пар

    // поэтому мы будем использовать хеш-функцию, определенную в библиотеке Boost

    unordered_map<pair<int, int>, int,boost::

              hash<pair<int, int> > > slopeMap;

  

    // цикл для каждой точки

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

    {

        curMax = overlapPoints = verticalPoints = 0;

  

        // цикл из i + 1, чтобы снова игнорировать ту же пару

        for (int j = i + 1; j < N; j++)

        {

            // Если обе точки равны, то просто

            // увеличиваем количество точек наложения

            if (points[i] == points[j])

                overlapPoints++;

  

            // Если координата х одинакова, то оба

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

            else if (points[i].first == points[j].first)

                verticalPoints++;

  

            else

            {

                int yDif = points[j].second - points[i].second;

                int xDif = points[j].first - points[i].first;

                int g = __gcd(xDif, yDif);

  

                // уменьшаем разницу по их gcd

                yDif /= g;

                xDif /= g;

  

                // увеличиваем частоту текущего наклона

                // в карте

                slopeMap[make_pair(yDif, xDif)]++;

                curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]);

            }

  

            curMax = max(curMax, verticalPoints);

        }

  

        // обновляем глобальный максимум по максимуму текущей точки

        maxPoint = max(maxPoint, curMax + overlapPoints + 1);

  

        // printf ("максимальная коллинеарная точка

        // который содержит текущую точку

        // являются:% d / n ", curMax + overlapPoints + 1);

        slopeMap.clear();

    }

  

    return maxPoint;

}

  
// Код драйвера

int main()

{

    const int N = 6;

    int arr[N][2] = {{-1, 1}, {0, 0}, {1, 1}, {2, 2},

                    {3, 3}, {3, 4}};

  

    vector< pair<int, int> > points;

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

        points.push_back(make_pair(arr[i][0], arr[i][1]));

  

    cout << maxPointOnSameLine(points) << endl;

  

    return 0;

}

Выход:

4

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

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

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

Подсчитайте максимальное количество очков на одной линии

0.00 (0%) 0 votes