|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초||512 MB||2||2||2||100.000%|
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 wellknown for having a lovely square beach that is composed of an N × N grid of square cells. You have brought your trusty shovel, which is able to dig up a K × K square subgrid of the beach. Your shovel, being trusty, can only dig up a K × 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 Si shells from the ith species in Si grid locations, with 1 ≤ Si ≤ 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 × 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?
The first line of input contains two integers N and K, (1 ≤ N ≤ 2500; 1 ≤ K ≤ N), the size of the beach and the size of the shovel, respectively.
The second line of input contains the integer M (0 ≤ M ≤ 105), the number of species of shells. The next M lines each represent species i and consist of the integer Si (1 ≤ Si ≤ 4) followed by 2 × Si more integers, which represent the grid positions (between (1, 1) and (N, N)) where the Si shells of that species are buried.
The next line contains T (1 ≤ T ≤ 10 000). 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:
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−4 of the judge’s answer.
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
0.88889 0.33333 0.44444 0.11111 0.00000
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 × 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.