Peaceful Sharing |
Two neighboring countries named Fobos and Dimos are in trouble with their natural resources. All the Gold mines are in Fobos and all the Coal mines are in Dimos and the Coal mines are always a good source of Diamond. So whenever Fobos needs Diamond she has to buy it from Dimos and vice versa. The peace loving Presidents (!) of these two countries meet to find out a way of sharing their resources and they decide very quickly to draw an Inter Country Mine Line (ICML), which is a straight-line that divides both the Gold mines and Coal mines equally. I mean if Fobos has 10 Gold mines and Dimos has 16 Coal mines then there will be 5 (=10/2) Gold mines and 8 (=16/2) Coal mines on one side of the ICML and the rest of the mines will be on the other side. Fobos will own the mines on one side of the line and Dimos will own the mines on the other side. But unfortunately, the number of both Gold mines and Coal mines are odd so they cannot be equally shared. Therefore, the Presidents have also decided that one Gold mine and one Coal mine will be on the ICML and those two special mines will be owned by both the countries. Now your job is two find these two special mines.
The input fine contains maximum 20 sets of inputs. The description of each set is given below:
Each set starts with an even integer N (
0 < N10000), which indicates how many mines are there in this case. Each of the next N lines contains two floating-point numbers x and y
(
0 < | x|,| y| < 10000) and (
| x|1.0), which indicates the location of a mine
in Cartesian coordinate system. The mines on the left side of y-axis
(negative x coordinate) are Gold mines and the mines on the right side
of y-axis (positive x coordinate) are Coal mines. The identifier
for each mine is in the order they appear in the input, starting from zero. But
the identifier series for Gold and Coal mines are different. So the first Gold
mine in the input file has serial 0, the second Gold Mine has serial 1
and similarly the first Coal mine in the input has serial 0, the second
Coal mine has serial 1 etc. You can assume that no three mines are on
the same line and no two mines are in the same place as mines are always
naturally distributed.
Input is terminated by a case where the value of N is zero. This case should not be processed.
For each set of input produce one line of output. This line contains the serial of output followed by two integers g and c, where g is serial of the Gold mine that is on the ICML and c is the serial of the Coal mine that is on the ICML.
Look at the output for sample input for details.
8 2397.3580 -1218.2430 3882.3760 -1892.8990 5038.0060 110.7790 4151.7250 2203.4090 1244.6460 3047.0100 -2567.4500 4835.3570 2964.6920 1447.6210 3742.6950 -1039.6250 8 3533.6490 -610.2480 -2707.0150 -3010.9940 -3440.8270 4392.1250 -54.2620 2227.8020 90.9070 2297.0630 -3236.5420 2868.4760 -1882.3930 -521.8910 3031.9350 -2618.9450 0
Case 1: 0 2 Case 2: 3 0