| 1 Ченченко Даниил Денисович, 12 января 2025 г. 12:39:20 |
| кто пришел смотреть ответ на задачу - 👎
|
|
|
| 2 Кактус, 15 июля 2022 г. 21:21:46 |
| Зачем так усложнять с расширением прямоугольников?
|
|
|
| 3 Артем Никифоров, 17 ноября 2019 г. 14:55:27 |
| Подскажите, как решить эту задачу через графы. Я просто здесь их не вижу
|
|
|
| 4 Молчан Егор Дмитриевич, 06 сентября 2019 г. 20:36:45 |
| Задача решается одним DFS, зачем тут СНМ?
|
|
|
| 5 Иван Михнович, 03 мая 2019 г. 22:59:11 |
| Обратите внимание, что объединение двух заповедников не подразумевает объединение двух прямоугольников. В резльтате получается один заповедник, в общем случае более сложной формы. СНМ - система непересекающихся множеств. Недооценённая структура данных, о которой в литературе упоминается только в описании алгоритма Крускала. Интересующимся рекомендую загуглить "СНМ викиконспекты".
|
|
|
| 6 Дестр Де, 07 марта 2016 г. 13:34:08 |
| При данных ограничения программу можно сделать и перебором. Получается порядка O(n^3), Если же n будет равно 1000, тогда перебор не пройдет. В этом случае лучше делать с помощью поиска по графам, там порядок O(n^2).
|
|
|
| 7 Бубоник, 17 ноября 2013 г. 19:38:31 |
Добавте тест пожалуйта:
2
-1 -5 1 5 0
-5 -1 5 1 0
Ответ 1
Моя программа выдает 2 и у меня Accepted
|
|
|
| 8 Ламтюгин Алексей Валерьевич, 27 октября 2012 г. 19:24:39 |
а более реальный тест:
0 0 1 1 0
-2 0 -1 -1 1,
тоже должен быть ответ 1.
|
|
|
| 9 Лебедев Алексей Евгеньевич, 28 августа 2012 г. 18:01:27 |
А почему если два прямоугольника касаются друг друга (имеют одну общую точку или одну общую прямую) они имеют "общие земли"? Площадь таких "общих земель" равна нулю, они их не имеют. А по решению задачи получается, что такие прямоугольники имеют общие земли.
Здесь считается, что если у прямоугольников есть общая точка, то они имеют пересечение, иными словами имеют общие земли, пусть и нулевой площади и даже нулевого линейного размера.
|
|
|
| 10 Волшебный конь, 24 июля 2012 г. 2:43:30 |
| не знаю причем тут графы - банально проверил пересечения для каждого нового с предидущими - все прошло
|
|
|
| 11 Артур, 13 декабря 2011 г. 3:17:17 |
Добавьте, пожулайсте, следующий тест. Два прямогуольника ведь пересекаются, даже если все вершины находятся "вне друг-друга" - крест например:
2
0 0 1 1 10
2 100 3 -100 0
Ответ должен быть 1, у них общие земли.
|
|
|
| 12 lolpwnZzzz, 19 августа 2011 г. 1:53:34 |
| не могу понять тест из примера: после "увеличения" имеем : (-2 9 7 -2) (-1 3 -4 0) (-4 1 -1 0), тоесть они все пересекаются. Однако ещё не понятно, как увеличить на -2, это значит уменьшить на 2? тогда не понятен ответ в примере.
|
|
|
| 13 ..., 28 апреля 2011 г. 22:50:11 |
Кстати да, решается и без графов, по сути. Правда я так и не понял как за N*logN . У меня пересечения ищутся за O(N^2).
Что такое CHM ? Гугл говорит что это Стрессовое Недержание Мочи, но мне кажется Кузьмин Алексей имел ввиуду что-то другое :)
|
|
|
| 14 ..., 28 апреля 2011 г. 22:39:56 |
| В 10ом тесте случай когда два прямоугольника имеют только 1 общую точку, и вопряки словам Админа, это не считается пересечением
|
|
|
| 15 Шевчук Евгений Николаевич, 05 марта 2011 г. 14:32:22 |
| Задача отличная! Правда решить ее можно и без теории графов - только с помощью геометрии и здравого смысла. O(n*logn) достигается не тяжело.
|
|
|
| 16 Суворов Константин Васильевич, 03 марта 2011 г. 23:24:41 |
| в общем я чит какой-то загнал, это печально
|
|
|
| 17 Суворов Константин Васильевич, 03 марта 2011 г. 22:45:47 |
"взял, да и проверил: попадает ли одна из вершин прямоугольников внутрь другого, а это легко."
А что насчет теста 1 0 0 3 3 и -4 -2 5 -1 0, например? точки не попадают, а прямоугольники пересекаются. мой АС выдает 2
|
|
|
| 18 Пипикин О. И., 11 февраля 2011 г. 20:54:42 |
уффф... делал 2 часа...но сдал с первого раза!!!(почти))))
|
|
|
| 19 Лизунов Михаил, 25 августа 2010 г. 20:40:00 |
| А не проще ли сделать граф, а потом запустить дфс?
|
|
|
| 20 Радченко Евгений Вячеславович, 10 апреля 2010 г. 18:42:17 |
Тут больше на геометрию похоже
Нет, на теорию графов больше. Это сначала немного геометрии, а потом идут компоненты связности в графах.
|
|
|
