问题描述

FJ的奶牛们最近发明了一个新的游戏，以此考验FJ。

所有N (2 <= N <= 50,000)头奶牛都站在平面内的某个整点上，奶牛1站在点(0,0)，FJ知道奶牛2与奶牛1的x坐标的距离(0 <= X_i <= 1,000,000)，以及她们y坐标的距离(0 <= Y_i <= 1,000,000)。

比如说，奶牛1与奶牛2的x、y坐标的距离为(3, 2)，那么奶牛2的位置可能为(3, 2)，(-3, 2)，(3, -2)或是(-3, -2)，因为奶牛1的位置为(0, 0)。随后，FJ依次被告知奶牛2与奶牛3的距离，奶牛3与奶牛4的距离，...，奶牛N-1与 奶牛N的距离。

Farmer John的任务是，在不改动各头奶牛间距离的情况下，通过合理地安排各头奶牛的位置，使奶牛N与奶牛1之间的x、y坐标距离的和最小。

这是一道提交答案题。对于每一组输入，保证能找到一种安排奶牛的方案，

使得奶牛N所在点恰好就是奶牛1所在点。如果你给出的奶牛安排方案中，奶牛N与奶牛1之间的x、y坐标距离的和为x，那么你的得分为(1000-x)/1000。输出的第一行按样例输出的格式，标明当前数据为第CASE (1 <= CASE <= 25)组。

输入数据在此下载.

程序名: cgame

输入格式:

• 第1行: 2个用空格隔开的整数：CASE、N
• 第2..N行: 第i+1行为2个用空格隔开的整数，分别为奶牛i与奶牛i+1的x、y坐标的距离

输入样例 (cgame.in):

1 5
2 6
3 1
1 4
4 3

输入说明:

一共有5头奶牛。奶牛1与奶牛2的距离为(2, 6)，奶牛2与奶牛3的距离为(3, 1)，奶牛3与奶牛4的距离为(1, 4)，奶牛4与奶牛5的距离为(4, 3)。

输出格式:

• 第1行: 按该格式输出1行信息：#FILE cgame ID，其中ID为数据编号
• 第2..N+1行: 输出程序求出的最优解中，各头奶牛的位置。第i行为2个用空格隔开的整数x、y，表示奶牛i的位置

输出样例 (cgame.out):

#FILE cgame 1
0 0
2 -6
5 -7
4 -3
0 0

输出说明:

这个输出可以拿到这个点的满分，因为奶牛1和奶牛N在同一个点，并且奶牛的相对位置没有违反输入中的规定。