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: 1 2 Next
Input precision
Posted by lxn 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?
Re: Input precision
Posted by Jane Soboleva (SumNU) 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.
Re: Input precision
Posted by lxn 31 May 2016 17:36
Thanks. The 6th test have numbers with 8 digits after decimal point.
Re: Input precision
Posted by lxn 1 Jun 2016 09:04
In test #13 there are numbers with 21 digits after decimal point
Re: Input precision
Posted by Orient 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?
Re: Input precision
Posted by lxn 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?
Re: Input precision
Posted by Orient 2 Jun 2016 23:01
Bad news if it is so.
Re: Input precision
Posted by lxn 3 Jun 2016 20:14
I have figured out that 1e-10 difference bewtween dx * dx + dy * dy is accepted
Re: Input precision
Posted by Jane Soboleva (SumNU) 3 Jun 2016 21:23
Good job, and thanks for the valuable info!
Re: Input precision
Posted by Orient 3 Jun 2016 21:42
You used Voronoi?
Re: Input precision
Posted by lxn 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 )
Re: Input precision
Posted by Orient 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?
Re: Input precision
Posted by Orient 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?
Re: Input precision
Posted by lxn 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
Re: Input precision
Posted by Orient 4 Jun 2016 17:05
If I use general precision arithmetic and algebraic numbers, then I get WA even being correct.
Re: Input precision
Posted by Orient 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.).
Re: Input precision
Posted by Orient 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.
Re: Input precision
Posted by lxn 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 Александр Пак)
Re: Input precision
Posted by Orient 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.
Re: Input precision
Posted by lxn 5 Jun 2016 10:53
Pages: 1 2 Next