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

Обсуждение задачи 1369. Тараканьи бега

How to implement this with Voronoi diagram
Послано al13n 28 фев 2012 00:18
Ok, I understand Fortune's algorithm for building Voronoi diagrams. But how to implement answering the nearest point queries? Can it be done without explicitly building full-featured Voronoi diagram and then using another sweeping line on it? I guess, the queries can be answered during building the diagram, without actually building the diagram. But how to generate events "a query point meets parabolic front"? Is it even possible in O(log n)?
Re: How to implement this with Voronoi diagram
Послано Orient 31 май 2016 20:45


Edited by author 10.11.2016 18:14