ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1464. Освещение

complexity
Послано UdH-WiNGeR 21 авг 2006 20:19
My solution is O(n*log n) and i wonder if there is a linear?
Re: complexity
Послано Walrus 21 авг 2006 21:13
My solution is O(n*log(n)) too...
Re: complexity
Послано Denis Koshman 27 авг 2008 09:45
I have an idea for linear-time solution, but I didn't implement it. Walk in coutner-clockwise order. While the lamp is in positive half-plane (i.e. we face inner side of a segment), add it. Once we face outer side (i.e. lamp is in negative half-plane), we cast darkness backwards in clockwise order from i+1'th vertex of outer side. Also, there will be no light until we reach its i'th angle. So, "forwards darkness" is skipped as long as we walk counter-clockwise forwads and "backwards darkness" pointer only deceases (walks only clockwise).