PROBLEM LINK:
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 
-
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
-
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). -
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
