Ежедневная часть (e) C++ # 107, Распространенная проблема на собеседовании: видимые точки

Учитывая список точек на 2D-плоскости, местоположение и угол [0..360], вернуть максимальное количество точек, которые можно увидеть из местоположения, используя поле зрения с шириной, заданной углом.

Точки не мешают друг другу, включая точки, находящиеся в одном и том же положении.

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

Решение

Давайте сначала рассмотрим, что мы пытаемся сделать здесь.

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

Поэтому первым шагом будет вычисление этих углов. Мы можем использовать std::atan2, который удобно обрабатывает угловые случаи, когда мы делим на ноль (для точек с одной и той же координатой x). Возвращаем угол в радианах.

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

Есть пара угловых случаев, с которыми нам нужно разобраться.

  1. мы всегда видим точки, на которых стоим
  2. наше поле зрения может охватывать конец массива рассчитанных углов, что мы можем исправить, продублировав массив, добавив 2*pi к каждому элементу
  3. дублирование вводит еще одну проблему, когда для поля зрения в 360 градусов мы дважды считаем элементы с минимальным углом

Наконец, мы возвращаем количество точек, на которых мы стоим, плюс размер максимального окна, которое мы нашли во время поиска в скользящем окне.

#include <vector>
#include <numbers>
#include <cmath>
#include <cstdint>
#include <algorithm>

struct Point {
    int x;
    int y;
};

int visible_points(std::vector<Point>& points, 
                   int angle, Point location) {
    // With angle == 360, we can see all points.
    if (angle == 360)
        return points.size();

    // Transform each point into an angle
   // (i.e. direction from location)
    std::vector<double> angles;
    int base = 0;
    for (const auto& p : points) {
        int x = p.x-location.x;
        int y = p.y-location.y;
        if (x == 0 && y == 0)
            // we can always see points we are standing on
            ++base;
        else
            // atan2 handles the corner cases of x == 0
            // returned angle is in radians
            angles.push_back(std::atan2(y,x));
    }
    if (angles.empty())
        return base;
   
    // Add another copy of the angles, adding 2*pi to each angle
    // this way, we don't have to deal with the field of view
    // crossing the boundary
    int sz = angles.size();
    for (int i = 0; i < sz; ++i)
        angles.push_back(angles[i]+2*std::numbers::pi);
    std::sort(angles.begin(), angles.end());

    // The angle in radians
    double rad = std::numbers::pi*angle/180;

    // With the preparation done, we can use a simple sliding window
    int64_t left = 0, right = 0;
    int64_t max = 0;
    while (right < std::ssize(angles)) {
        // While the angle is less than our field of vision
        // - advance the right border
        if (angles[right]-angles[left] <= rad) {
            max = std::max(max, right-left+1);
            ++right;
            continue;
        // While the angle is more than our field of vision
        // - advance the left border
        } else if (left < right) {
            ++left;
        }
    }
    // Maximum visible + points we are standing on
    return max + base;
}

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