Description
Mickey is assigned a task to help the puppies to escape by travelling from the south-west corner of a grid to the north-east corner undetected by the set of motion detectors deployed by Cruella. There are k motion detectors (1<=k<=300) which are placed on the grid points and can detect any motion within a given distance, d , from the detector. Here we adopt L1 metrics for distance measurements, i.e., the distance between two points (x1, y1) and (x2, y2) is | x1 - x2| + | y1 - y2| . For example, consider the 9×9 grid in the figure below, if the detecting distance of the two detectors, marked with a solid circle, is 3, there exists a tour from (0, 0) to (8, 8) (for example the diagonal is an undetectable tour); however, if the distance is four, there would be no such tour.
Cruella decides to make it more difficult to escape by setting the detecting distance of the detectors randomly. For each grid, Cruel would flip coins to decide the detecting distance for all the detectors in that grid. Given the probability distribution of the detecting distance d and a series of grids, your task is to write a program to decide for each input grid the probability that it contains an undetectable tour.
Each grid is N×N where 3<=N<=10000 , and each grid point in the grid is denoted by a pair of integers, (x, y) , where 0<=x , y<=N - 1 . The probability distribution is specified by a sequence of ordered pair (d1, p1),(d2, p2),...,(dm, pm) where 1<=m<=100, 1<=di<=2(N - 1) , and each pi has at most three digits after the decimal point. To make it a probability distribution we also have the property that Σpi = 1 .
Input
The first line of the input file contains an integer indicating the number of test cases to follow, there will be at most 5 test cases. For each test case, the first line contains two integers, N and m separated by a space. Followed by m lines to specify the probability distribution, each line consists di, pi . Followed by k lines of the positions of detectors in the form x ,y which is the coordination of the detector. The case ends with a line containing `-1'.
Output
For each test case, output the probability that the grid contains a undetectable tour.