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.
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.
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 suppose the
area of the gray region is A1 and
area of the other region is A2. The
total city area is A = A1 + A2. So
the gray part ideally should have
A1
A × 11 air purification plants but
in reality it has 6 air purification
plants. So inconsistency index for
the gray part is


A1
A −
6
11


. Similarly, inconsistency index for other
part is


A2
A −
5
11


. The whole city can be divided into two parts in infinite possible 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) .
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
4 5 8 8
5 6
0 5
8 4
2 2
4 9
0 8
4 4
3 9
0 0 0 0
Sample Output
Scenario 1: 0.339430 solve in c++