Разве unordered_map не должен иметь только два параметра? - PullRequest
Новая
       63

Разве unordered_map не должен иметь только два параметра?

0 голосов
/ 29 апреля 2019

Этот вопрос касается нахождения коллинеарных точек из набора точек.

Во-первых, я не понял, как выглядит slopeMap и неупорядоченная карта?Разве карта не предполагает только ключ и значение (map<key, value>)?В этом конкретном коде 

unordered_map<pair<int, int>, int,boost:: 
          hash<pair<int, int> > > slopeMap;

Насколько я понимаю, у него есть пара в качестве ключа и int после него, что должно быть значением, но тогда оно точно не заканчивается?

ПОЛНЫЙ КОД: 

using namespace std; 

// method to find maximum colinear point 
int maxPointOnSameLine(vector< pair<int, int> > points) 
{ 


    int N = points.size(); 
      if (N < 2) 
        return N; 

    int maxPoint = 0; 
    int curMax, overlapPoints, verticalPoints; 

    // here since we are using unordered_map  
    // which is based on hash function  
    //But by default we don't have hash function for pairs 
    //so we'll use hash function defined in Boost library 
    unordered_map<pair<int, int>, int,boost:: 
              hash<pair<int, int> > > slopeMap; 

    // looping for each point 
    for (int i = 0; i < N; i++) 
    { 
        curMax = overlapPoints = verticalPoints = 0; 

        // looping from i + 1 to ignore same pair again 
        for (int j = i + 1; j < N; j++) 
        { 
            // If both point are equal then just 
            // increase overlapPoint count 
            if (points[i] == points[j]) 
                overlapPoints++; 

            // If x co-ordinate is same, then both 
            // point are vertical to each other 
            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); 

                // reducing the difference by their gcd 
                yDif /= g; 
                xDif /= g; 

                // increasing the frequency of current slope 
                // in map 
                slopeMap[make_pair(yDif, xDif)]++; 
                curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]); 
            } 

            curMax = max(curMax, verticalPoints); 
        } 

        // updating global maximum by current point's maximum 
        maxPoint = max(maxPoint, curMax + overlapPoints + 1); 

        // printf("maximum colinear point  
        // which contains current point  
        // are : %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; 
}

ГДЕ 

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}

Я также хотел логическое предложение.Как я мог изменить этот код так, чтобы вместо того, чтобы возвращать число, определяющее максимальное количество коллинеарных точек, фактически сохранялось любое коллинеарное значение в некоторой форме структуры данных, которую я могу использовать позже?

Источники: Подсчет максимальных точек одной линии

1 Ответ

0 голосов
/ 29 апреля 2019

Разве карта не предполагает только ключ и значение (карту)?

На самом деле, std :: unordered_map имеет несколько дополнительных параметров шаблона. Третий параметр - хеш.

Как я мог изменить этот код так, чтобы вместо возврата числа который определяет максимальное количество точек коллинеарных, чтобы на самом деле хранить любые точка, которая является коллинеарной в некоторой форме структуры данных, которую я могу использовать позже?

С целочисленными координатами это проще, чем с плавающей точкой (из-за проблем с точностью). Я предполагаю, что у вас есть массив 2D точек p. Одним из способов было бы для каждых двух пар точек p[i] и p[j], чтобы ваш ключ был парой dX, dY , приведенной к младшей форме (где dX = p[j].x - p[i].x и dY = p[j].y - p[i].y). Тогда вашим значением может быть std::set<int>, содержащее совпадающие индексы i и j.

...