| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 144 |
| 3 | nik_exists | 144 |
| 5 | Errichto | 139 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | DNR | 132 |
| 9 | AmShZ | 131 |
| 10 | Dominater069 | 129 |
Долгое время не могу решить задачу. Дано 100 000 прямоугольников. Стороны параллельны осям координат. Все координаты целые и убираются в 4 байта. Нужно найти на сколько замкнутых фигур разбивают плоскость эти прямоугольники и найти площадь наибольшей фигуры. за N^2 не катит. Думал над деревом отрезков, но не могу придумать, как его применить.
Помогите, пожалуйста..
Что подразумевается под замкнутой фигурой?
Подразумевается область, ограниченная сторонами некоторых прямоугольников, внутри которой не проходят другие прямые, я полагаю
Так или иначе, видимо, сканирующая прямая должна помочь.
А можно ссылку на задачу? Если, конечно, ссылка существует.
Не думаю. Эта задача была позавчера на корпоративном контесте компании Samsung (только для сотрудников). Я так полагаю, автор блога в нем участвовал, как и я=). Ссылка-то существует, но она приватна и зайти по ней можно, только если ты зарегистрирован в системе. Так что, если корейцы, конечно, не взяли эту задачу с топкодера, ссылку на задачу получить не удасться. Да я и не понимаю зачем она, если человек написал её условие, предварительно еще и переведя на русский язык=). Могу, если хочешь, написать оригинал условия на корейском или английском=).
UPD: решение неверно, прошу прощения
Я не вдавался в детали, но сканлайн действительно помогает.
Все операции умеет делать декартово дерево (максимум на отрезке, добавить элемент в середину, удалить элемент). Еще надо очень аккуратно смотреть на совпадающие y-координаты. Возможно, я где-то ошибся, извините, если так.
Маловато информации поддерживаешь. Как обрабатывать замкнутые компоненты с дырками внутри (например, бублик, получающийся из двух кнцентрических квадратов)? Тебе как-то нужно помнить информацию о связности тех фрагментов, которые у тебя сейчас есть.
Да, ты прав, я чушь написал. Надо как-то поддерживать какой отрезок в какой компоненте, но это пока непонятно как, потому что компонент может быть квадрат и при открытии-закрытии прямоугольника куча всего меняется.
Сегодня на межфакультетской в КПИ была упрощенная версия. Надо было найти количество пар прямоугольников, которые имеют хоть одну общую точку.
А это не задача на раскраску? Мы принимаем на вход координаты прямоугольника (х1,у1), (х2,у2), красим область плоскости, ограниченную этими точками, в цвет равный номеру запроса, храним все полученные покраски в дереве отрезков, потом каким-то образом определяем число различных сочетаний цветов на одном участке плоскости(сканлайном, видимо) и пытаемся параллельно считать площадь каждой новой найденной области и хранить максимальную площадь.
Поясните, пожалуйста, что именно имеется в виду под разбиением плоскости. Прямоугольник считается закрашенным или нет? Иными словами, на тесте
количество областей будет 1 или 3 (не считая внешней грани)?
А на тесте
2, 9 или еще сколько-то? (тест — четыре прямоугольника, опоясывающих квадрат 1 1 2 2).
Если правильное понимание — то, в котором прямоугольники закрашены, то задача сводится к тому, чтобы понять, какие связные компоненты образуют прямоугольники (легко делается сканлайном), а потом отдельно посчитать площадь каждой из них, а также всех внутренних частей (их уже может быть квадрат, это я еще не знаю, как делать быстро).