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?

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.

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

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

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

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?

Bad news if it is so.

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

Good job, and thanks for the valuable info!

You used Voronoi?

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 )

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?

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?

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

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

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.).

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.

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 Александр Пак)

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