74 - ZOJ Monthly, January 2009 - F
Watashi likes rejudge, but he likes mixed juice much more than rejudge ^-^
Watashi's girlfriend makes a bottle of mixed juice, but for some reason, she has to leave for a while and she tells watashi to wait her back to drink the juice togethor. Of course watashi is very excited, so he hold the bottle to have a good look at, but, unfortunately, he breaks the bottle on the ground! So he is very frustrated, but luckly, he know that his girlfriend made the bottle of mixed juice using N different kinds of juice, each kind of them contains XAi apple juice, XBi orange juice(0 <= XAi, XBi <= 1), the other is water. And at this moment, he has M different kinds of juice, each kind of them contains YAi apple juice, YBi orange juice(0 <= YAi, YBi <= 1), the other is water. If he can make another bottle of mixed juice using these M kinds of juice, maybe his girlfriend will not notice what happened and will not punish him^-^. He knows his girlfriend is clever enough to find out the truth when the juice cannot be made by the original N kinds of juice. Watashi doesn't know how his girlfriend made the juice, so he can only try to make the juice randomly. To forbid being punished by his girlfriend, he wants to know the probability he make another bottle of mixed juice and his girlfriend will not notice. (Thus, if his girlfriend find out that the newly made juice cannot be made by the original N kinds, watashi will be punished.)
To make the thing more clearly, we assume that every kind of mixed juice, no matter in the set of all kinds of original one's generated or in the set of all kinds of newly made, has a equal-probability.
Input consist of multiple cases.
Each case starts with a line contains two numbers N and M(3 <= N, M <= 3000). The following N lines, each line contains two real numbers XAi and XBi(0 <= XAi, XBi <= 1, 0 <= XAi + XBi <= 1). Then the following M lines, each line contains two real numbers YAi and YBi(0 <= YAi, YBi <= 1, 0 <= XAi + XBi <= 1).
Each case one line, output the probability of watashi to finish the bottle of juice but his girlfriend doesn't notice. Retains three decimals.
3 3 0.05 0.1 0.3 0.1 0.1 0.3 0.2 0.1 0.4 0.1 0.2 0.3 3 3 0.05 0.05 0.10 0.10 0.20 0.20 0.10 0.10 0.21 0.21 0.30 0.30
Author: FAN, Yuzhe
Source: ZOJ Monthly, January 2009