квадратный раствор

Question

Следующая проблема была задана в конкурсе по программированию, который закончился.

Программа Squarepie

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

Сначала добавьте все ребра в структуре, которая сначала сортируется по длине, а затем по их положению. У меня были две разные структуры для х и у ребер. Найдите внешний прямоугольник и добавьте его в стек. Теперь для каждого прямоугольника в стеке найдите, есть ли какой-либо пересекающийся край. Если да, разделите этот прямоугольник на два по этому ребру и добавьте оба в стек. Если не удалось найти биссектрису, добавьте область прямоугольника в приоритетную очередь. В конце выведите элементы из очереди с приоритетами.

Теперь мне интересно, есть ли более быстрое решение?

Редактировать: - Прикрепление моего решения.

Мое окончательное решение

Answer 1

Все выглядит хорошо, кроме getLargestRect(), который вы действительно слишком усложняете. Просто верните rectangle(minX, minY, maxX, maxY). Вы можете найти мин и макс в линейном времени. Текущая реализация - O (n ² ), когда все строки имеют одинаковую длину.

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

При взгляде на горизонтальную линию h все вертикальные линии с y1 < h.y && y2 >= h.y сохраняются на карте по значению x. Текущая горизонтальная линия образует прямоугольники со всеми вертикальными линиями от map[h.x1] до map[h.x2]. Две внешние линии простираются за h.y, но все средние должны заканчиваться на h.y и поэтому удаляются с карты после того, как площадь их прямоугольников была вычислена. Вертикальные линии, которые необходимо добавить на карту для каждой горизонтальной линии, эффективно находят путем сортировки вертикалей по их значению y1.

Вот код:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) < (b) ? (b) : (a))

using namespace std;

class Horizontal
{
public:
    int x1, x2, y;

    Horizontal(int x1, int x2, int y) : x1(x1), x2(x2), y(y) {}

    static bool comp(const Horizontal & a, const Horizontal & b)
    {
        return a.y < b.y;
    }
};

class Vertical
{
public:
    int x, y1; // no need to store y2

    Vertical(int x, int y1) : x(x), y1(y1) {}

    static bool comp(const Vertical & a, const Vertical & b)
    {
        return a.y1 < b.y1;
    }
};

long long total = 0;
int vertI = 0; // index of next vertical to add to currentVerts
map<int, int> currentVerts; // currentVerts[5] = y1 of the vert line with x=5
vector<Vertical> verticals;
vector<Horizontal> horizontals;
vector<int> solutions;

void readInput();
void processHorizontal(Horizontal & line);

int main()
{
    cout.precision(10);

    readInput();

    sort(verticals.begin(), verticals.end(), Vertical::comp);
    sort(horizontals.begin(), horizontals.end(), Horizontal::comp);

    // process the lines  (start at i = 1 to ignore the top one)
    for (int i = 1; i < horizontals.size(); i++)
    {
        processHorizontal(horizontals[i]);
    }

    sort(solutions.begin(), solutions.end());

    for (int i = solutions.size() - 1; i >= 0; i--)
    {
        cout << (double) solutions[i] / total << "\n";
    }
}

void readInput()
{
    int n;
    cin >> n;

    int x1, x2, y1, y2;

    for (int i = 0; i < n; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;

        if (x2 < x1) swap(x1, x2);
        if (y2 < y1) swap(y1, y2);

        if (x1 == x2) verticals.push_back(Vertical(x1, y1));
        else horizontals.push_back(Horizontal(x1, x2, y1));
    }
}

void processHorizontal(Horizontal & horiz)
{
    // add all vert lines which start above horiz to currentVert
    for ( ; vertI < verticals.size() && verticals[vertI].y1 < horiz.y;
            vertI++)
    {
        int x = verticals[vertI].x;
        currentVerts[x] = verticals[vertI].y1;
    }

    map<int, int>::iterator left = currentVerts.find(horiz.x1);
    map<int, int>::iterator right = currentVerts.find(horiz.x2);

    map<int, int>::iterator i;
    map<int, int>::iterator next;

    for (i = next = left; i != right; i = next)
    {
        next++;

        int width = (*next).first - (*i).first; // difference in x
        int height = horiz.y - (*i).second; // difference y
        int area = width * height;

        total += area;
        solutions.push_back(area);

        if (i != left)
        {
            // if i is not the start it must be a short
            // line which ends here, so delete it
            currentVerts.erase(i);
        }
        else
        {
            // if it is left, cut the rectangle at horiz.y
            // by modifying the start of the line
            (*i).second = horiz.y;
        }
    }
}