Computer network is a wonderful thing which developed very quickly. Its development speed is out of our imagination. Some years ago, a computer network consists of just several computers connected together. But nowadays, there are billions of computers connected directly or indirectly to the Internet. And our ACM Regional Contest are held on a intranet whose scale is not too large and not too small. Ring network is a connecting way of computer network. Ring network ensures that there exists a communication circuit between any two computers in the network, but when we want to join a new computer to the network, the problem arises. The network administrator has to disconnect the cable of communication between two computers first, and then place the new computer between the two computers (that is, computer A and computer B). At last, he has to connect the new cables of communication between computer A and the new computer and between the new computer and computer B. After carrying out several such operations on a small ring network, maybe the network administrator are not very sure about the circuit of the network. Suppose that you are the miserable administrator. And suppose you know the computers’ coordi- nates and the cables of the ring network. But now you want to join a new computer to the network. Of course you know the coordinate of the new computer. Maybe you hope that you needn’t to determine which cable in the ring network to be disconnected by yourself. So you are required to write a program to accomplish such a thankless task. Your progarm will determine which cable to be disconnected, so that the total amount of the new cables needed will be minimized. Note: If the original cable being disconnected is long enough, you needn’t make two new cables, but just to make a new cable and use the original one instead. And you could use the original cable once at most. That is, you have to make a new cable at least. The length of the cable, in the ring network between computer A and computer B, is the distance between computer A and computer B. For example, here is a ring net work consists of 5 computers, as the figure on the left shows: You are required to join a new computer whose coordinate is (8, 3.5) to the network. The method to minimize the total amount of the new cables needed is shown as the figure on the right. The dotted line in the figure is the new cable needed. Input The input file will consist of a series of data sets. Each data set will begin with a integer n (1 < n ≤ 512) indicating the number of computers in a ring network. A value of ‘0’ for the number of computers
2/2 indicates the end of input, and this data set should not be processed. Then follows n pairs of floats, (xi,yi) (−4096 ≤ xi,yi ≤ 4096), which give the coordinates of the computers in the network. There are cables between each computer and its preceding one, except the first computer. To construct a ring network instead of a linear network, there are a cable between the first computer and the last computer. And then follows a pair of floats, (xnew,ynew) (−4096 ≤ xnew,ynew ≤ 4096) which give the coordinate of the new computer to join the ring network. Output The output for each set begins with a line which tells the case number (they are numbered sequentially starting with 0, just as Case #0, Case #1, etc.). This is followed by a line which tells the cable to be disconnected. In this line you should output the coordinates of the computers which connect with the cable to be disconnected, just as ‘Disconnect between (x1,y1) and (x2,y2)’. Then the following line tells the total amount of the new cable(s). The output of this line should be ‘Minimum length of new line: x.xx’. Here ‘x.xx’ is the total amount of the new cable(s). The output for each data set are separated by blank lines. The output of computers’ coordinates and the total amount of the new calbes(s) should be accurate to 2 decimal places. Sample Input 5 1 1.5 5 1 2 3 6 3.5 7 2 8 3.5 0 Sample Output Case #0 Disconnect between (6.00,3.50) and (7.00,2.00). Minimum length of new line: 2.00