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

Pages: Previous 1 2
Re: Input precision
Posted by Shen Yang 21 Oct 2016 14:51
to avoid decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.
Re: Input precision
Posted by Shen Yang 21 Oct 2016 14:51
sorry for so many dumplicate post with so fucking network

Edited by author 21.10.2016 14:59
Re: Input precision
Posted by Shen Yang 21 Oct 2016 14:51
to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.
Re: Input precision
Posted by Shen Yang 21 Oct 2016 14:51
to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.
Re: Input precision
Posted by Shen Yang 21 Oct 2016 14:52
to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.
Re: Input precision
Posted by Orient 10 Nov 2016 18:07
I thought about Delanau triangulation. I have nD implementation of Quickhull algo, which can give me triangulation, when applied to projection onto paraboloid. Bit it is not too hard to imagine bad case for BFS on triangulation graph. E.g. well known concentric points. It is the same bad case as for quadtree.

Edited by author 10.11.2016 18:12
Re: Input precision
Posted by Orient 20 Dec 2017 21:49
Does your last solution use this algorithm?
Re: Input precision
Posted by Shen Yang 20 Dec 2017 21:57
NO,  my AC sol directly find voronoi diagram but when Location the point, you mustn't find the intersection point of x==x0  instead you should find the nearest Thiessen polygons directly using Euclid distance to sort it..

in a word you should use original point as much as you can to inprove your accuracy

btw seems there is some clever k-d tree sol also get AC...

Edited by author 20.12.2017 21:58
Re: Input precision
Posted by Orient 20 Dec 2017 22:59
What do you think, are top 3 solution implemented via Voronoi?

I implemented Fortune's (https://github.com/tomilov/sweepline), but I can't overcome precision errors in case of regular grids and concentric points, even if I use a little cheating: I modify input by rotation on some small angle. Some of points became a points-in-general-positions.

Then I use something like this (http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf), but invented by myself - it is much simplier for Voronoi diagram.

I interested to talk with you (I will not bother you much), can you give any contact?

Edited by author 21.12.2017 19:51
Re: Input precision
Posted by Shen Yang 21 Dec 2017 16:29
you can contact me through 441766573@qq.com  my qq is always online...
Re: Input precision
Posted by Orient 21 Dec 2017 21:10
Shen Yang wrote 21 December 2017 16:29
you can contact me through 888888888@qq.com  my qq is always online...
You can remove the number and add me to your contacts =).
Pages: Previous 1 2