Discussion @ 1369. Cockroach Race @ Timus Online Judge

lxn Input precision [30] // Problem 1369. Cockroach Race 30 May 2016 15:18

There is a restiction for X and Y values: −10000.0 ≤ x, y ≤ 10000.0. Does .0 (sigle zero) means that only one digit after the decimal point is possible? Or if there any restriction for number of digits after the decimal point?

Jane Soboleva (SumNU) Re: Input precision [1] // Problem 1369. Cockroach Race 30 May 2016 15:51

You can check it on your own... Throw a division by zero or reach a memory limit or whatever, if you meet a number with more than one digit. If you still reach the same test, then there's no such numbers.

lxn Re: Input precision // Problem 1369. Cockroach Race 31 May 2016 17:36

Thanks. The 6th test have numbers with 8 digits after decimal point.

lxn Re: Input precision [27] // Problem 1369. Cockroach Race 1 Jun 2016 09:04

In test #13 there are numbers with 21 digits after decimal point

Orient Re: Input precision [26] // Problem 1369. Cockroach Race 1 Jun 2016 11:37

lxn wrote 1 June 2016 09:04

In test #13 there are numbers with 21 digits after decimal point

It bothers you? Do you want to talk about it?

lxn Re: Input precision [25] // Problem 1369. Cockroach Race 2 Jun 2016 08:06

This is a test case with only 6 digits after decimal point:
2
999.969732 999.984915
1414.181493 0
1
0 0
And it needs about 20 digitd precision to resolve it corectly, Doubles can fail on such tests. Using 21 digits it is possible to create tests which can be solved correctly using long arithmetic only. Does this problem requires to compare distances with no error, or there is an accepted tollerance?

Orient Re: Input precision [24] // Problem 1369. Cockroach Race 2 Jun 2016 23:01

Bad news if it is so.

lxn Re: Input precision [23] // Problem 1369. Cockroach Race 3 Jun 2016 20:14

I have figured out that 1e-10 difference bewtween dx * dx + dy * dy is accepted

Jane Soboleva (SumNU) Re: Input precision // Problem 1369. Cockroach Race 3 Jun 2016 21:23

Good job, and thanks for the valuable info!

Orient Re: Input precision [21] // Problem 1369. Cockroach Race 3 Jun 2016 21:42

You used Voronoi?

lxn Re: Input precision [20] // Problem 1369. Cockroach Race 4 Jun 2016 10:36

I've got accepted with O(N * M) solution. But in my main idea i use voronoi and have WA17 - there are some precision errors in voronoi building, but i hope that i can fix it )

Orient Re: Input precision // Problem 1369. Cockroach Race 4 Jun 2016 12:21

lxn wrote 4 June 2016 10:36

I've got accepted with O(N * M) solution.

O(N * M) for 1.762 seconds??? Is it Voronoi with following "modification": instead of binary tree you use just a linked list? N sweep line motions * M increemnts of iterator during binary search in linked list (but still log(M) parabolas' intersections)? Or something else?

Orient Re: Input precision [18] // Problem 1369. Cockroach Race 4 Jun 2016 12:28

lxn wrote 4 June 2016 10:36

But in my main idea i use voronoi and have WA17 - there are some precision errors in voronoi building, but i hope that i can fix it )

What is the cause of WA? Symmetic cases (more then 3 sites on vertex?)?
Is it true, that there are four cockroaches maximum may be close to each sweet piece?

lxn Re: Input precision [17] // Problem 1369. Cockroach Race 4 Jun 2016 15:24

1) 1.762 - is voronoi solution. O(N * M) works more than 3 seconds. There were smome implementation issues. My O(N * M) just check eahch to each with no precalcs.

2) definitely no. points (-5, 0) (-4, -3) (-3, -4) (0, -5) (3, -4) (4, -3) (4 3) (3 4) (0 5) (-3 4) (-4 3) have the same distance equal to 5 from the point (0, 0). Using a floating point values there are possible thousands of cockroaches close to some sweete pieces

Edited by author 04.06.2016 15:25

Orient Re: Input precision // Problem 1369. Cockroach Race 4 Jun 2016 17:05

If I use general precision arithmetic and algebraic numbers, then I get WA even being correct.

Orient Re: Input precision // Problem 1369. Cockroach Race 5 Jun 2016 00:05

lxn wrote 4 June 2016 15:24

1) 1.762 - is voronoi solution.

Can you say is the following algorithm right?:
1.) Firstly lexicographically sort all the cockroaches and all the sweet pieces.
2.) In first pass, make Voronoi for cockroaches using Fortune algorithm. Voronoi data struct is graph of vertices and edges. For each edge there are pointer to "left" site and pointer to "right" site. For each vertex there is a set of pointers to edges, which supported by this vertex.
3.) Vertices are produced by algorithm in previous step, are already sorted lexicographically (or sort them otherwise).
4.) In second pass, events are sweepings of vertices and sweepings of sweet pieces. For each edge there is bounding box. We can track appearing and lefting of bounding boxes for each edge and infer the belonging of each sweet pieces for each cell.

I am very doubted with 4.).

Orient Re: Input precision [14] // Problem 1369. Cockroach Race 5 Jun 2016 00:20

lxn wrote 4 June 2016 15:24

1) 1.762 - is voronoi solution.

Another possible algorithm is "inline" version of Fortune's algorithm: during sweep line motion if parabolic arc disappears, then we have a pair of edges, that meets in corresponding new vertex. Check all sweeped sweet pieces for belonging to cone, supported by this two edges. I some sweet piece is inside (or on the edge (2 cockroaches), or matches the vertex (greater then 2 number of cockroaches are closest)), then move it from list of already sweeped sweet pieces to result.

lxn Re: Input precision [13] // Problem 1369. Cockroach Race 5 Jun 2016 08:16

1) I think that both of this algos are incorrect. Bounding boxes of the edges is not good idea because some sweets can be out of any bounding box
2) Check all sweets when parabolic arc disappears needs to much time. There could be the sitation when all of the sweets are located in the same voronoi cell, and is is located in such place the there are a lot of cells before
PS
I don't that it is good idea to discuss here a correct solution.
We can discuss it out of timus forum for example in vk.com (my name is Александр Пак)

Orient Re: Input precision [12] // Problem 1369. Cockroach Race 5 Jun 2016 10:18

There are a plenty of your namesake in vk.com. It is almost impossible to distinct you from the others.

lxn Re: Input precision [11] // Problem 1369. Cockroach Race 5 Jun 2016 10:53

https://vk.com/lxnbald

Shen Yang Re: Input precision // Problem 1369. Cockroach Race 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.

Shen Yang Re: Input precision // Problem 1369. Cockroach Race 21 Oct 2016 14:51

sorry for so many dumplicate post with so fucking network

Edited by author 21.10.2016 14:59

Shen Yang Re: Input precision // Problem 1369. Cockroach Race 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.

Shen Yang Re: Input precision // Problem 1369. Cockroach Race 21 Oct 2016 14:51

Shen Yang Re: Input precision [6] // Problem 1369. Cockroach Race 21 Oct 2016 14:52

Orient Re: Input precision // Problem 1369. Cockroach Race 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

Orient Re: Input precision [4] // Problem 1369. Cockroach Race 20 Dec 2017 21:49

Does your last solution use this algorithm?

Shen Yang Re: Input precision [3] // Problem 1369. Cockroach Race 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

Orient Re: Input precision [2] // Problem 1369. Cockroach Race 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

Shen Yang Re: Input precision [1] // Problem 1369. Cockroach Race 21 Dec 2017 16:29

you can contact me through 441766573@qq.com my qq is always online...

Orient Re: Input precision // Problem 1369. Cockroach Race 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 =).

Discussion of Problem 1369. Cockroach Race