Ежедневный бит (е) C ++ # 56, Общая проблема интервью: максимальное количество точек на линии.

Сегодня мы рассмотрим распространенную задачу интервью C++: максимальное количество точек на линии.

Учитывая список точек, представленных целочисленными координатами x и y, определите максимальное количество точек, которые можно соединить одной прямой линией.

Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на проводник компилятора с парой тестов: https://compiler-explorer.com/z/ej4GhGx3b.

Решение

Критическое наблюдение состоит в том, что любые две точки будут определять линию (пересекающую эти две точки). Это напрямую приводит к очевидному решению. Мы можем перебирать все пары точек, подсчитывая, какие другие точки также лежат на этой линии. К сожалению, этот подход O(n³). Мы можем сделать лучше.

Давайте вместо этого привяжем одну точку и рассмотрим линии, которые мы можем провести через эту точку. Затем каждая уникальная линия будет идентифицирована своим углом. Если мы повторим все остальные точки, максимальная линия, проходящая через наш якорь, будет соответствовать углу с максимальным количеством экземпляров.

Мы можем использовать неупорядоченную карту от угла до подсчета, что позволит нам обновить подсчет за O(1), а поскольку нам нужно рассматривать все точки как потенциальные точки привязки, и для каждой мы перебирая все остальные точки, мы получаем сложность O(n²).

Чтобы представить угол, мы можем построить тип простой дроби, позаботившись о его нормализации, чтобы каждый уникальный угол имел уникальное представление (что приводит к одному и тому же хешу). Чтобы его можно было использовать в качестве ключа в неупорядоченной карте, мы должны предоставить operator== и специализацию для std::hash.

#include <numeric>
#include <vector>
#include <unordered_map>
#include <cstdint>

struct Point {
    int x;
    int y;
};

struct Slope {
    Slope(int num, int den) {
        // Normalize slope so that every angle corresponds 
        // to a distinct value.
        int gcd = std::gcd(num,den);
        // Horizontal & vertical lines end up with gcd == 0.
        if (gcd != 0) num_ = num / gcd;
        else if (num != 0) num = 1;
        if (gcd != 0) den_ = den / gcd;
        else if (den != 0) den = 1;
        // Normalize so that the denominator is positive.
        if (den_ < 0) {
            num_ *= -1;
            den_ *= -1;
        }
    }
   // Required for unordered_map.
    friend bool operator==(const Slope& left, const Slope& right) {
        return left.num_ == right.num_ && left.den_ == right.den_;
    }
private:
    int num_;
    int den_;
    friend struct std::hash<Slope>;
};

// Required to use Slope as the key in unordered_map.
template <> struct std::hash<Slope> {
    std::uint64_t operator()(const Slope& slope) const {
        return std::hash<int>{}(slope.num_) ^ 
          (std::hash<int>{}(slope.den_) << 1);
    }
};

int max_points(const std::vector<Point>& points) {
   // Initialize with 0 if empty or 1 if not.
    unsigned max = !points.empty();
    // For each point, find a line going through that point 
    // that has the most other points on it.
    for (const auto& point : points) {
        // Count number of instances of each Slope.
        std::unordered_map<Slope,unsigned> count;
        for (const auto& other : points) {
            if (&other == &point) continue;
            ++count[{other.x-point.x,other.y-point.y}];
        }
        // Update the global maximum.
        for (auto &[key, value] : count)
            if (value + 1 > max) max = value + 1;
    }
    return max;
}

Откройте решение в Compiler Explorer.