Problem link:
PREREQUISITES:
Geometry, Expected value, Combinatorics
PROBLEM:
Given N * M grid, and C circles of unit radius, we need to print the expected area covered by circles, in any randomly chosen A * A square from the grid.
EXPLANATION:
The question basically asks us to take average of the area covered by the circles in all possible A * A squares. Let us formulate it below and then simplify it later:
Total squares of size A (say X) = (N - A + 1) X (M - A + 1)
f(x) = (Σ_{i = 1}^{X} Area of circles in square i) / X
Since there are A * A cells in a square, we can name them from 1 to A * A.
f(x) = (Σ_{i = 1}^{X} Σ_{j = 1}^{A * A} Area of a circle in cell j of square i) / X
The above formula states that for each square, we see how much does each of it’s cell’s area is covered by circle and sum over it. Instead, we can rephrase this and count for each cell, it’s portion that is covered by circle and add it as many times as the square it might be present in. We are basically changing our focus from “first choosing a square and then considering it’s cells” to “fix a cell and count total squares it contributes to”.
Now, lets see how can we count the total area covered by cell if a circle’s center is present on some of it’s four vertices. Cell in consideration is with dark border. Three cases are possible:-
1.) When there are two circles with centers on adjacent vertices and remaining two vertices are free. In this case we can find the covered area with integration. It turns out to be: Π / 6 + √(3) / 2.The colored part is eliminated
2.) Second case is when the there are two circles centered diagonally opposite vertices of a cell. In this case, the entire cell gets covered by the circles and hence area comes out to be 1.
3.) Third case is that there is only one vertex of cell having a circle centered at it. Now, the cell has Π / 4 area of cell covered by circle.
We have skipped some trivial cases like having 0 vertex with circle centers (When answer is trivially 0) or when there are more than 2 circle centers on the square vertices (where answer is 1 using case (2) and basic pigeon-hole principle).
For each cell we can find the area it has covered by circles using the formula mentioned above, multiplied with the total number of square of size A it can be present in. Add this to answer for each cell and then take average by dividing it with X i.e total squares possible.
You can refer to editorialist’s code here for a sample implementation of this idea.
Time Complexity: O(N log N)
Space complexity: O(N)