Editorial for APIO '10 P3 - Signaling - DMOJ: Modern Online Judge

Editorial for APIO '10 P3 - Signaling

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The problem description is: Given $N$ ~N~ points on a 2D plane, we guarantee that any three points are not in a line and any four points are not on a circle. Randomly pick $3$ ~3~ different points to make a circle, and compute the average number of points that are inside or on the circle. We assume that each point has the same probability to be chosen.

Our goal is to compute the average number of points that are covered by the circle. In fact, we only need to compute the sum of points that are covered by any circle and divide the result by $\binom N 3$ ~\binom N 3~ to get the exact answer for our problem.

Algorithm 1: A brute force solution for this problem is to enumerate any three different points and calculate their corresponding circumcircle. Then we can count how many points are inside or on the circle in $\mathcal O(N)$ ~\mathcal O(N)~ time. Clearly, this solution works in time $\mathcal O(N^4)$ ~\mathcal O(N^4)~.

Now our task is to count the number of quadruplets $(A, B, C : D)$ ~(A, B, C : D)~ such that point $D$ ~D~ is inside the circumcircle of $A, B, C$ ~A, B, C~. Let's consider the position relation between $D$ ~D~ and $A, B, C$ ~A, B, C~:

Seeing the above figure, we can deduce that if point $D$ ~D~ is in area I, II, or III, then the sum of the angle $D$ ~D~ and the angle of the opposite point must be $>180^\circ$ ~>180^\circ~ since the interior angle is always larger than the corresponding circumferential angle. For example, if $D$ ~D~ is in area I, then $\angle ADB + \angle ACB > 180^\circ$ ~\angle ADB + \angle ACB > 180^\circ~ and the four points must form a convex quadrangle. Similarly, if $D$ ~D~ is outside the circle, the sum of the angle $D$ ~D~ and the corresponding opposite angle must be $<180^\circ$ ~<180^\circ~. And another case is $D$ ~D~ is inside the triangle $ABC$ ~ABC~, then the four points must form a concave quadrangle.

Hence let's consider every quadrangle we get from the set of points, note that two quadrangles are distinct if and only if the set of the $4$ ~4~ points are different ( $4$ ~4~ points can construct different quadrangles if one point is inside the triangle of another $3$ ~3~ points). We can see that

if it's convex, then there are $2$ ~2~ ways to pick $3$ ~3~ points to make a circle so that the circle contains the remaining point. This is because the sum of the $4$ ~4~ angles is equal to $360^\circ$ ~360^\circ~ and no $4$ ~4~ points are on a circle, there must be exactly a pair of opposite angles such that their sum is greater than $180^\circ$ ~180^\circ~. For example, if $\angle A + \angle C > 180^\circ$ ~\angle A + \angle C > 180^\circ~ in a quadrangle $ABCD$ ~ABCD~, then point $C$ ~C~ must be in the circle of $ABD$ ~ABD~ while $A$ ~A~ must be in the circle of $BCD$ ~BCD~.
if it's concave, then there is exactly $1$ ~1~ way to pick $3$ ~3~ points to make a circle such that the circle contains the remaining point. In this case, the $4^\text{th}$ ~4^\text{th}~ point must be in the triangle of the other $3$ ~3~ points.

Let $P =$ ~P =~ the number of convex quadrangles and $Q =$ ~Q =~ the number of concave quadrangles. Our new goal is to compute the value of $2P+Q$ ~2P+Q~ and it is straightforward that $P+Q = \binom N 4$ ~P+Q = \binom N 4~. There are many ways to compute $P$ ~P~ or $Q$ ~Q~ or any linear combinations of $P$ ~P~ and $Q$ ~Q~ in $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~ or $\mathcal O(N^3)$ ~\mathcal O(N^3)~ time, then we can get $2P+Q$ ~2P+Q~. Next, we will give a very simple method to compute $4P+3Q$ ~4P+3Q~.

For any quadrangle $T$ ~T~ and a vertex $v$ ~v~ of $T$ ~T~, if we can draw a line through $v$ ~v~ such that all other $3$ ~3~ points lie in one side of this line, then we say that the vertex $v$ ~v~ is "good".

We can see that for any convex quadrangle, all vertices are "good" while there are only $3$ ~3~ "good" vertices in a concave quadrangle except the innermost point. If we can count the number of "good" points for any $4$ ~4~ points, then we have got the value of $4P+3Q$ ~4P+3Q~.

Algorithm 2: enumerate a point as $v$ ~v~, and sort all other points by their polar angles with respect to $v$ ~v~. Then we can scan all other points in the order and maintain the number of points such that the angle between it and the current point is $<180^\circ$ ~<180^\circ~. Then we can count the number of quadrangles in which $v$ ~v~ is a "good" vertex in $\mathcal O(N)$ ~\mathcal O(N)~ time. For each point $v$ ~v~, it takes $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time to sort all other points by polar angles and $\mathcal O(N)$ ~\mathcal O(N)~ time to scan all points to get the answer. So the total running time is $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~.

Till now, we have got a complete algorithm in $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~ time. In fact, there are many similar methods to compute a linear combination of $P$ ~P~ and $Q$ ~Q~ and after we sort all other $N-1$ ~N-1~ points, we can enumerate two points to calculate the result to get an $\mathcal O(N^3)$ ~\mathcal O(N^3)~ algorithm which can pass $70\%$ ~70\%~ of the test cases.

Comments

There are no comments at the moment.