ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1369. Cockroach Race

How to implement this with Voronoi diagram
Posted by al13n 28 Feb 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
Posted by Orient 31 May 2016 20:45


Edited by author 10.11.2016 18:14