|
J |
Air
Pollution Problem Input: Standard Input Output: Standard Output |
|
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 air-purification 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 
air purification
plants but in reality it has 6 air purification plants. So inconsistency index
for the gray part is 
. Similarly, inconsistency index for other part is 
. 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
Output for 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 |
Scenario
1: 0.339430 |
Problemsetter: Shahriar Manzoor, Special Thanks: Derek Kisman