Canadian Computing Olympiad: 2015 Day 2, Problem 3

It's time for a vacation! You are sick and tired of C shells, so you decide to become a seashell collector.

For your vacation, you have decided to visit the beautiful island nation of Cartesia. It is well-known for having a lovely square beach that is composed of an $N\times N$ grid of square cells. You have brought your trusty shovel, which is able to dig up a $K\times K$ square subgrid of the beach. Your shovel, being trusty, can only dig up a $K\times K$ subgrid that is entirely within the beach.

There are $M$ undiscovered species of shells hidden under certain grid cells. Specifically for each $i$, there are $S_i$ shells from the $i^{th}$ species in $S_i$ grid locations, with $1\le S_i\le 4$. For each distinct species that you dig up and bring back home, you can sell it to a scientist back home for one dollar. Multiple shells of the same species don't add extra value.

Complicating matters is a glorious dodo bird running around the beach. At a given moment, it may decide to bury an egg in a grid cell (including grid cells that have eggs or shells already). The bad news is that if the $K\times K$ subgrid dug up by your shovel includes a dodo egg, the scientists will become annoyed that you are harming endangered species, and nobody will pay you anything.

After all is said and done, you decide to sit back, go back to programming, and simulate the digging instead. You will be computing the probability that your scoop, when chosen uniformly from all valid possible scoops, will make at least a given minimum profit (to pay off your student loans) at different points in time. Who wants to get all sweaty from shoveling on a beach anyway?

Input Specification

The first line of input contains two integers $N$ and $K$, ($1\le N\le 2500$; $1\le K\le N$), the size of the beach and the size of the shovel, respectively.

The second line of input contains the integer $M$ ($0\le M\le {10}^5$), the number of species of shells. The next $M$ lines each represent species $i$ and consist of the integer $S_i$ ($1\le S_i\le 4$) followed by $2\times S_i$ more integers, which represent the grid positions (between $(1,1)$ and $(N,N)$) where the $S_i$ shells of that species are buried.

The next line contains $T$ ($1\le T\le 10000$). Each of the next $T$ lines represent one specific point in time (from oldest to newest) and each line has one of the following two forms:

• 1 $A_i$ $B_i$ ($1\le A_i,B_i\le N$), meaning that the dodo just buried an egg in the grid cell $(A_i,B_i)$;
• 2 $V_i$ ($1\le V_i\le {10}^9$), meaning we would like to calculate the probability that a random dig at this point in time has profit in dollars $\ge V_i$. Note that no shells or eggs are actually removed or added when this probability is calculated.

For at least 15% of the marks for this question, $N\le 40$ and all update operations occur before all query operations.

For an additional 25% of the marks for this question, all update operations will occur before all query operations.

Output Specification

For each query operation, output on one line the probability that a random scoop would contain at least the desired number of different types of shells.

Your answer must be within ${10}^{-5}$ of the judge's answer.

Sample Input

4 2
3
3 1 1 2 3 4 2
3 1 4 2 3 3 2
4 2 1 2 4 4 1 4 4
6
2 2
2 3
1 2 3
2 2
2 3
2 4

Output for Sample Input

0.88889
0.33333
0.44444
0.11111
0.00000

Explanation for Sample Output

Initially, we have the following arrangement of shells (with the first shells in the input being labelled as 1, and so on):

and our shovel will scoop up a $2\times 2$ square of cells. Thus, there are 9 possible scoops.

With no eggs present, 8 of the 9 scoops contain at least two species of shells and 3 of the 9 scoops contain three species of shells.

An egg is then dropped into the cell that contains 1, 2.

Then, 4 of the 9 scoops contain at least two species of shells and no eggs and only 1 scoop (the bottom-leftmost scoop) would contain all three species of shells and no eggs. The final output indicates there are no scoops which contain 4 different species of shells.