Блог пользователя akhan42

Автор akhan42, история, 3 года назад, По-русски

Задача геометрическая. Мы решим ее за n ^ 2 * log n время.

Назовем линию шириной t, полоской шириной t или просто полоской. Пусть у нас есть какое то решение и наша полоса не содержит на краю никакие точки. Тогда мы ее можем двигать до тех пор пока она станет содержать на краю у себя какую то точку. Теперь решение будет в форме что у нас есть какая то точка P, через нее мы провели полоску (так что P на краю полоски) и эта полоска содержит максимальное количество точек. Давайте выберем точку P, и заметим что полоску можно определять через угол и соответственно вращать на все 360 градусов и это будут различные полоски, давайте представлять такие полоски через угол.

Ключевое наблюдение в задаче, пусть есть другая точка Q. Вот пока мы вращаем нашу полоску начиная с какого то угла альфа она будет содержать точку Q. Потом пройдя какой то угол бетта она перестанет ее содержать. То есть существует отрезок [альфа, бетта] и если взять любой угол из этого отрезка и представить через нее полоску, то полоска будет содержать точку Q. То есть мы сведем задачу к задаче о максимальном пересечений отрезков, которая решается за n * log n.

Некоторые детали. Таких отрезков на самом деле два и они не пересекаются. Пусть альфа это угол соединяющий точки P и Q (считаем через арктангенс и получаем значение от -180 до 180). Поворот между бетта и альфа определяется через арксинус t / длина(PQ), нарисуйте на бумаге и поймите. Второй же отрезок будет таким. Альфа2 у второго отрезка будет центрально симметричен альфе1 первого, и чтобы получить бетта2 нужно поворачивать на тот же угол, только в обратную сторону.

Есть некоторые технические детали поиска максимального пересечения отрезков на окружности (то есть всех углов от -180 до 180). Они таковы. Пусть скажем у вас есть n отрезков, тогда у вас 2 * n концов. Упорядочите ваши углы запоминая каким отрезкам они принадлежали и были ли они началом или концом отрезка. Скажем получились упорядоченные значения -179, -150, 0, 50, 130, 170. Теперь считаете сколько отрезков содержать точку перед -179. То есть те чьи правые концы по кругу перешли так что теперь они в значений меньше своих левых концов. После этого идите поочередно через каждую точку от -179 до 170. Если вы перешли через точку представляющую левый конец значит вы вошли в новый отрезок (увеличиваете свой counter). Если же перешли правый конец уменьшаете counter.

Код который аксептиться на icpc.kattis.com я его почистил и за комментировал.

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

#define mp make_pair
using namespace std;

long double eps = 1e-9;
long double SCALE = 180.0 / 3.141592653589793238463;

long double get_angle(long double x1, long double y1, long double x2, long double y2)
{
    return atan2l(x2 - x1, y2 - y1) * SCALE;
}

long double get_rotation(long double x1, long double y1, long double x2, long double y2, long double t)
{
    long double dx = x2 - x1;
    long double dy = y2 - y1;
    long double gipotenuza = sqrt(dx * dx + dy * dy);
    if(t >= gipotenuza)
        return 90;
    return asinl(t / gipotenuza) * SCALE;
}

long double symmetry(long double angle)
{
    if(angle <= 0)
        angle += 360;
    return angle - 180;
}

long double rotate_by_angle(long double angle, long double rot)
{
    angle += rot;
    if(angle > 180)
        angle -= 360;
    else if(angle <= -180)
        angle += 360;
    return angle;
}

int find_max_intersection(vector<pair<long double, long double> > &sl)
{
    set<pair<long double, int> > tochki;
    for(int i = 0; i < sl.size(); i++) {
        tochki.insert(mp(sl[i].first + eps, 2 * i)); /// left end of a segment
        tochki.insert(mp(sl[i].second - eps, 2 * i + 1)); /// right end of a segment
    }

    int ct = 0;
    /// compute the number of segments which contain -179.99... point
    /// (those which right end is less than left end)
    for(int i = 0; i < sl.size(); i++)
        if(sl[i].second < sl[i].first)
            ct += 1;
    int maxct = ct;

    for(auto iter = tochki.begin(); iter != tochki.end(); ++iter)
    {
        ct += -2 * (iter->second % 2) + 1; /// add counter 1 if entering segment, else deduct
        maxct = max(maxct, ct);
    }
    return maxct;
}

int main()
{
    int n, t, x, y;
    vector<int> xs;
    vector<int> ys;
    cin >> n >> t;
    for(int i = 0; i < n; i++)
    {
        cin >> x >> y;
        xs.push_back(x);
        ys.push_back(y);
    }

    int gl_max = 0;
    for(int i = 0; i < n; i++)
    {
        vector<pair<long double, long double> > sl;
        for(int j = 0; j < n; j++)
        {
            if(i == j)
                continue;
            /// define line via angle, so entering some angle it contains the point j
            /// then leaving another angle it stops containing the point j
            long double main_angle = get_angle(xs[i], ys[i], xs[j], ys[j]);
            long double rot = get_rotation(xs[i], ys[i], xs[j], ys[j], t);
            long double rev_main_angle = symmetry(main_angle);

            /// add two segments in which line contains the point j
            sl.push_back(mp(rotate_by_angle(main_angle, -rot), main_angle));
            sl.push_back(mp(rev_main_angle, rotate_by_angle(rev_main_angle, rot)));
        }
        /// now we need to compute maximum segment intersection
        int maxct = find_max_intersection(sl) + 1;
        gl_max = max(gl_max, maxct);
    }
    cout << gl_max;
}

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится