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. Figure: The figure above shows a typical scenario that is stated in this problem. There are total five Gold mines and seven Coal mines. So when they are equally divided into two parts then both sides have two Gold mines and three Coal mines. The ICML passes through the other Gold and Coal mine. If the total number of each type of mines is odd and no three mines are on the same line then ICML is always unique. The goal of this problem is to find the two mines that are on the ICML. Input 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 < N ≤ 10000), 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

2/2 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. Output 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. Sample Input 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 Sample Output Case 1: 0 2 Case 2: 3 0