Есть задача следующего содержания:
Задано на плоскости множество из N прямоугольников, стороны которых параллельны осям координат, при этом каждый прямоугольник задается координатами левой нижней и правой верхней его вершин. Составить алгоритм определения наибольшего натурального числа К, для которого существует точка плоскости, принадлежащая одновременно К прямоугольникам.
Проще говоря, надо найти место, где одновременно пересекаются больше всего прямоугольников.
Примечание: эффективным считается алгоритм, число действий которого пропорционально O(n²).
Мой код изначально выглядел так:
struct Rectangle
{
Point first;
Point second;
Rectangle(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0)
{
first.x = x1;
first.y = y2;
second.x = x2;
second.y = y1;
}
// Переопределение координат
// для задания через левую верхнюю
// и правую нижнюю точки.
void RedefineCoords()
{
swap(this->first.y, this->second.y);
return;
}
};
bool CheckIntersection(Rectangle a, Rectangle b)
{
return
(a.first.x <= b.second.x &&
a.second.x >= b.first.x &&
a.first.y >= b.second.y &&
a.second.y <= b.first.y);
}
int main()
{
int maxIntersections = 0;
for (int i = 0; i < quantity - 1; i++)
{
int countIntersections = 0;
for (int j = 0; j < quantity; j++)
{
if (CheckIntersection(rectangles[i], rectangles[j]))
countIntersections++;
}
if (countIntersections > maxIntersections)
maxIntersections = countIntersections;
}
cout << maxIntersections << endl;
}
Но я понимаю, что так просто это не посчитать. Подскажите, пожалуйста, какой алгоритм стоит использовать (необязательно nlog n
-оптимальный), чтобы решить эту задачу?
N^2
или заNlogN
? Для первой сложности есть элементарный алгоритм. Для второго заметание с сортированным деревом (упрощенный вариант Бентли-Оттмана).N^2
вполне достаточно, для понимания картины происходящего