ANDOOR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitalij Kozhukhivskij
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Computational Geometry: Circle-Cirle Intersection, Line-Circle Intersection

PROBLEM:

You have completely black coordinate 2D plane. Then you color at white the region enclosed by the rectangle with the vertexes at the points (0, 0), (W, 0), (0, H), (W, H). Then for several circles you color at black the regions enclosed by each of the circle. You need to find the perimeter of the remaining white figure, but only that part of the perimeter that lies strictly inside the original rectangle.

If someone is confused by this formulation here is another one that actually almost reveals the whole solution. For each circle you need to find the length of its boundary inside the rectangle that not covered by other circles and output the sum of these values over all circles.

QUICK EXPLANATION:

For each circle we will erase from its boundary several arcs covered by other circles or by outer part of the rectangle. But at first we should consider trivial corner cases: the circle lies completely outside the rectangle or the circle is completely covered by some other circle. In this case we skip this circle. I predict that many contestants actually have missed one of these cases.

Now assume that circle is non-trivial and denote it by C. We will work with arcs as with polar angle segments. So initially we have one segment (-Pi, Pi], where Pi = 3.1415926… is well-known constant. Then for each other circle C’ we at first check whether it intersects with C. If no, we move on (note that we already check that C is not covered completely by any other circle). Otherwise we find the intersection points of C and C’ and add the corresponding arc on C to the list of arcs that should be erased. When all circles are processed we consider sides of the rectangle. For the given side we should find the part of C that lies in the outer half-plane corresponding to this side and add the corresponding arc to the list.

When adding arcs, note that some arcs could cover the cut point Pi, in this case you should add two arcs to the list. When the list of arcs to erase is ready we sort corresponding segments of angles and use standard algorithm (some kind of sweep-line algorithm) to find their union. Then the answer for the current circle is R * (2 * Pi − L), where R is its radius and L is a union of erased arcs.

PRECISION ISSUES:

I feel like we will have many complains due to this. But let me try to prevent most of them :slight_smile:

  1. General tip: always try to avoid floating point computations. In this problem the main pitfall is that points are given as floating values and most of the contestants deal with them as they are. But the only safe way to deal with the input values is to multiply them by 100 and round them (rounding is important) and then deal only with integers values except some places where we can’t avoid floating point arithmetic. Hence if you have WA and do not use this suggestion any complains will be rejected :slight_smile:

  2. Now I describe the most evil bug that could be in this problem, when you are not using integer values and do some unsafe check. Assume that you are checking whether the circle intersects with the right side of the rectangle. If the parameters of the current circle are (X, Y, R) then your check could look like:
    if (fabs(W - X) < R) do arc erase
    Due to floating point issues this check could sometimes work when circle is tangent to this line. For example when R = 0.1, W = 1 and X = 0.9 this indeed happens. AFAIK some contestants contrived to avoid this by switching to long double type (they even got AC after this). IMHO it is some kind of tambourine dance (it is idiom in Russian :)). At least such switch is compiler depended because at some compilers double = long double.
    But we move on. So in the case of equal numbers from our point of view they somehow stored in double as non-equal numbers. So in our example we have
    0.1 = 0.10000000000000001
    and
    1 − 0.9 = 0.099999999999999978.
    The difference is just about 2e-17. As mentioned above we consider this circle as intersecting with the side of the rectangle and add some arc to the list of arcs. Namely the arc [-A, A] will be added in this case, where
    A = acos((W − X) / R).
    “So what?” you think probably now: the negligible intersection should add negligible arc. Like hell it will! Just calculate acos((1 − 0.9) / 0.1). It is about 2.1e-8, which is quite far from negligible. To understand this we should involve some properties of inverse cosine function. Namely, acos(1 − x) = sqrt(2 * x) * (1 + o(1)), when x tends to zero (it has very simple geometric proof). Hence when x was just around 1e-17 the acos(1 − x) is not very small. To ensure that this indeed may lead to a bug check it out this example. As wee see the circle is tangent to the side of the rectangle but due to the incorrect comparison we cut some considerable part from the circle that leads to absolute error of about 2.8e-5 in the output, which is 28 times larger than allowed error 1e-6. (The code assume that the door is the half-plane :-[, but it should work in general case too).

  3. The same bug could also occur when we try to intersect tangent circles. It is geometrically clear that very small difference between distance and sum of radii could lead to considerable arcs cut from the circles. Hence you should either use comparison using integers to check tangent circles properly or use wise epsilon if you still want to use doubles.

EXPLANATION:

Details will be provided soon. As of now refer to tester’s solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

SPOJ - 3863. Area of circles - VCIRCLES
SPOJ - 8073. The area of the union of circles - CIRU

5 Likes

And that is exactly why you will absolutely never find any quality contest problem solely asking for absolute error instead of an absolute/relative combination.

5 Likes

IMHO this issue with acos() fair to be a trick of the high quality problem. If you are so smart then suggest some “quality contest problem” having some precision stuff. I am sick of your unfair critic comments! Really!

5 Likes

Hey guys , don’t fight ! I made 100 wrong submissions and am still laughing and maybe I will learn a few things after reading this editorial . I am still to figure out my mistake . Last two days of the contest I solved 4-5 easy problems from easy section of practice section to uplift my mood after my terrible time loss / energy loss and no points gained in this problem . Cheers , keep the energy positive :slight_smile:

10 Likes

^I agree with this completely!!!

We are here to learn new things and enjoy problems, not fight with eachother! :))

Also, this community works hard as nobody other does and the problems are BETTER than some found at CGJ imho… So, let’s just enjoy this

I think that precision problems are a fair game in a 10-day contest with an unlimited number of attempts. Actually, they deserve a place here.

However, I’m still not sure where triplem’s last WA submission failed. Long doubles saved the day in the end, but his solution seems to handle all the mentioned precision issues correctly.

@admin please give the test cases for this problem as soon as possible . it will be of great help.

3 Likes

Hi Anton, at the contest page you promised you’d provide me (after the contest) with the only test case where my AC submission differs from my “best WA” submission. How do I get it? Thanks!

Actually, he exactly traps in the situation explained in the paragraph 2.
Note that he performs the intersection check with right side as
if (circ[i][0]+circ[i][2]>W) {
where circ[i][0] and circ[i][2] are doubles.
While he uses integers testcirc[i][j] only for some intermediate checks.

This is one of reasons why I angry with him: I exactly explained in the editorial his bug but he still consider this problem as crappy precision problem. BTW I still didn’t forget his comments for MAXCIR and CLOSEST.

2 Likes

1000 1000 2
10.00 10.00 0.02
674.94 756.87 1000.00
Our answer is 28.5976846
While your answer is 28.5976824

although i have spent quite a few days on this problem, even hated it, but finally when i have solved it, i almost liked it. i have learned a few things about floating point precision and that’s my gain on this problem.

2 Likes

Thanks. It’s like a balm to the soul :slight_smile:
Actually we did not expect any such precision issues with this problem.
I was quite busy with other problems so forgot to consider this problem carefully from this perspective.
I’ve only noticed that we ask for 1e-11 relative error in the worst case.
Since working double precision is 1e-16 I was absolutely sure that all will be fine.
The acos() trick was noticed only in the middle of the contest.

Actually I did some additional investigation. So you could expect some evilest problem ever on precision from me in the near future :wink:

2 Likes

Thanks a lot! Turns out I was very lucky with my AC submission. In fact, my AC submission has more rounding errors, but they pull in opposite directions :slight_smile:

Ahhh! 125 submissions and no AC (Failed after passing 7 test files). Yet to know my mistake. Could you help me @anton_lunyov .

P.S:Code Ok with Test case given above.

Thanks!

Turns out using (22.0/7.0) gives a different pie value than acos(-1) , causing the precision problem for my solution. Shouldnt 22.0/7.0 be more accurate ?

I’m still not clear on why either of the provided solutions are correct.

You have shown in the editorial that if the intersection between two circles is actually 0, then using doubles for comparisons can result in a WA because tiny errors in doubles can cause a tiny error in the size of the intersection, but enough to cause a WA.

Consider two circles which do intersect. You have no choice but to use doubles, and tiny errors in doubles will cause a tiny error in the length of the intersection. Unless I’m mistaken, there could be just over 2 million intersections all which contribute to the final sum, so each intersection needs to be calculated to better than 10^-12 accuracy.

Can you prove that both provided solutions do this? Trig functions will quickly escalate any errors, as you also noted.

Feel free to correct my logic if this is not true.

1 Like

so just googled it, and 22/7 is actually the least accurate fraction for PIE. Huge lesson learned here.
Great question all together! Lots to learn. Geometry + Programming is one of my weak points.

1 Like

I apologise for the above post; it wasn’t called for. (Though I’m not sure what you mean regarding MAXCIR/CLOSEST, in MAXCIR I mentioned an issue with unsigned integers that you/everyone else seemed to agree with, rather than any complaining?) My more thought-out response is below.

1 Like

I think you cannot prove that these solution are 100% correct, but one may reason as follows to “show” that a big error is unlikely to occur:

  • each precision error can be seen as a random value say in interval (-eps,eps)

  • if we sum n such values: by CLT, the probability that we get an error bigger than 3epssqrt(n) is negligible.

Ah, and the edge cases only make a difference due to the fact you don’t get the negatives cancelling them out.

Still, with n being a million, and the fact that you have to raise the probability of success to the power of 1000 test cases…

//