|
|
|
|
|
|
|
| 1 Неизвестный, 16 ноября 2022 г. 0:45:58 |
| координаты могут ли быть меньше нуля?
|
|
|
| 2 Матус Даниил Дмитриевич, 21 декабря 2020 г. 9:03:05 |
| 20000*n*log(n)
|
|
|
| 3 Чопонов Данияр, 09 июля 2020 г. 16:15:58 |
| 20000*(log(n)+n)
|
|
|
| 4 Дмитриев Дмитрий Андреевич, 15 января 2020 г. 12:47:48 |
| Нет, ну за O(n*n*log n) прям легко... А вот как за n log n сделать, аж интересно стало
|
|
|
| 5 Яндулов Богдан, 12 июня 2019 г. 6:32:43 |
N*N*log(N) примерно получается
При желании можно O(nlogn)
|
|
|
| 6 Яндулов Богдан, 30 июля 2018 г. 19:51:04 |
Сдал оооочень тупым способом: при пересечении 2 прямоугольников удалял из очереди тот, который больше и добавлял 1-4 прямоугольника так, чтобы пересечение отпадало. 15 случаев и 2,5к символов кода. Не советую так делать.
С таким способом ещё и оценку количества операций сложно получить.
|
|
|
| 7 Тер-Саркисов Богдан Олегович, 29 июня 2018 г. 0:33:19 |
Можно поднять ограничения до N <= 1000
Можно поднять ограничения до 10^5, а на хорошем процессоре или с Time Limit несколько секунд - и до 10^6.
|
|
|
| 8 Поляков Лев Алексеевич, 27 июня 2018 г. 18:32:52 |
Сначала задается левый нижний угол, а затем правый верхний? У меня вроде все правильно, но выходит Runtime error :(
Цитата "координаты двух противоположных углов прямоугольника"
|
|
|
| 9 Хвощевский Алексей Владимирович, 15 января 2018 г. 21:24:15 |
| подход аналогичный #467
|
|
|
| 10 Старожилов Сергей Алексеевич, 29 июля 2015 г. 13:52:03 |
| Для меня весь подвох заключался в том, что я думал, что сначала задаётся нижний левый угол, а потом верхний правый угол прямоугольника. Вывод: нужно внимательно читать условия)
|
|
|
| 11 Адрианов Тимофей, 01 июля 2013 г. 16:29:01 |
тут геометрии 0. уж скорее сортировки и последовательности.
Не соглашусь, геометрия присутствует: например, проверка принадлежности одного прямоугольника другому.
|
|
|
| 12 Прищенко Богдан Олегович, 13 января 2010 г. 23:02:47 |
Да уж, прога, которая использует абсолютно неверный алго и работает лиш в случае, если нету перекрытия 3 и больше прямоугольников в одном месте, доходит до 9 теста, прога, которая не принимает во внимание то, какие углы на входе - до 3 теста, и даже прога, котора сортирует не тот массив - до 8 теста. Такие вот утешительные первые тесты:)
Может ограничения поднять? Или хотя бы тестов побольше сделать, при текущих ограничениях? У меня написан О(N^4), и он получает АС и 0,113с времени. Смешно, можно кое-какие лишние вещи дописать, чтоб было О((N^4)*log(N)), и все равно можно будет сдать. По моим подсчетам и тестинге на локалке и других сайтах, даже при ограничениях в 100 можно дать тест, на котором лобовой О(N^4) покажет 0.2 секунды или даже немного больше.
|
|
|
| 13 Чабаненко Владислав Дмитриевич, 24 октября 2009 г. 14:35:02 |
какой ответ при
2
1 1 3 3
4 0 6 2 ?
Ваши прямоугольники имеют площадь 4 каждый и не пересекаются, поэтому их объединение равно их сумме, т.е. ответ 8.
|
|
|
| 14 Снетков Санька, 20 февраля 2009 г. 15:40:36 |
А правильно ли я понял условие что каждый прямоугольник касается или лежит не весь или весь лежит в другом прямоугольнике?
Нет, прямоугольники могут быть отдельно, т.е. не касаться друг друга и не пересекаться своими площадями.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
