We the mankind have polluted the atmosphere all the time. That is why now in the year 2100 AD, people have to build cities covered with transparent glasses (Very hard glass though). This has to be done because people cannot survive in open air now and the artificial cover helps us to build an artificial atmosphere that is not polluted. But this system has not allowed us to remain 100% safe from the adverse atmosphere outside. Sometimes there are cracks in the glass cover and then people near that crack are supplied oxygen masks but not everyone in the city can be saved in that way. Whenever there is a crack in a certain part of the cover that part of the city is separated from the rest of the city with an invisible straight wall that prevents airflow from one part of the city to the other part, so the other part remains safe. But this creates another type of problem that will be explained somewhere below. The city that we are talking about in this problem has 100 million people and they emit a lot of carbon-di-oxide (CO2). The city is circular in shape (Can be considered an exact circle). As the citizens are continuously polluting the city atmosphere, many air purification plants are placed around the city in a scattered way. These plants add oxygen and remove carbon-di-oxide from the air. But the number of plants in the city is exactly according to the requirement of the city: Not much more than the required numbers. This is because (a) The establishment cost of plants is very high (b) Too many plants reduces the CO2 level of air to a very low level, which can be harmful for the trees within the city (Yes there are very few trees in the city as well). So it may happen that when the city is divided into two parts one part may have less air purification plant than necessary and the other part may have more air purification plans than necessary. In other words inconsistency is created for the construction of the walls. For example, in the figure on the left, the city (Denoted by a circle) has 11 air purification plants inside it (Denoted by small green dots). Cracks are seen in one side of the city wall (Marked with black arrow) and so a wall is instantly created (pointed with a blue arrow and denoted with a thin black straight line). Now sup- pose the area of the gray region is A1 and area of the other region is A2. The total cityareaisA=A1+A2. Sothegray part ideally should have A1 × 11 air pu- A rification plants but in reality it has 6 air purification plants. So inconsistency in- dex for the gray part is A1 − 6 . Sim- A 11 Figure: The city has 11 air-purification plant which are just enough for the requirement of the city. When the city is divided into two parts the left part has 5 and the right part has 6 airpurification plants. But the left part has larger area so it has less air-purification plants than required. ways. Given the coordinates of the air purifying plants in 2D Cartesian coordinate system, your job is to find maximum possible inconsistency index considering all possible divisions. This will help the city designers, as they will try to place the air purifying plants in such locations so that maximum possible inconsistency is minimum. You can assume that the area that an air pollution plant occupies is zero, compared to the area of the total city and the dividing wall can be modeled as an straight-line (Zero thickness) . ilarly, inconsistency index for other part is A2 − 5 . Thewholecitycanbedi- A 11 vided into two parts in infinite possible
2/2 Input The input file contains maximum 220 sets of input. But most of the input cases are not extreme. The description of each set is given below: First line of each set contains four integers Cx, Cy, R (0 < R ≤ 6000) and N (5 ≤ N ≤ 2000). Here (Cx,Cy) is the coordinate of the center of the city, R is the radius of the city and N is the total number of air purification plants in the city. Each of the next N lines contains two integers (xi,yi) (0 ≤ xi, yi ≤ 10000), which denote location of one air purification plant. Any three purification plants will not fall on the same line. Input is terminated by a line containing four zeroes. Most of the input cases are not extreme. There are only 6 cases where N = 500, 4 cases where N = 1000 and only one case where N = 2000. In all other cases N ≤ 100. The total size of input file is less than 150 kilo-byte and has less than 14000 lines in total. Output For each set of input produce one line of output. This line contains the serial of Scenario followed by a floating-point number. This floating-point number denotes the maximum possible inconsistency index and has six digits after the decimal point. Sample Input 4588 56 05 84 22 49 08 44 39 0000 Sample Output Scenario 1: 0.339430