情景:带围巾是际霸2的游戏大厅地图作者。今天,他在编写一张游戏地图的规则时,遇到了难题:一局游戏中会有从3到14名不等的玩家加入这局游戏,并且随机出生在这张地图上。他想要编写的这条游戏规则,是将这些玩家尽量平均地分配到三个阵营里面交战。三个阵营各自有各自的主基地。他决定按照这些玩家到这个主基地的距离来为这些玩家分配队伍。而且要使得人数尽量均匀,才能让游戏相对公平。但是带围巾在着手解决这个问题的时候,被卡住了。你能帮帮他吗?
题目:在给定的坐标系(256*256)内,现在有3到14个随机的点(Xi,Yi),1<=i<=imax,3<=imax<=14,和3个固定点(Xpn,Ypn),1<=n<=3。不知道随机点和固定点的具体位置,但是你能够得到这3到14个点各自到这三个固定点的距离。请将这3到14个点根据它们到这三个点的距离,尽量均匀分配到三组,优先使得每组点到这组对应的固定点的距离之和最小,并且使得三组点的距离总和最小。每个点的到固定点的距离将会连续输入,输入三个数据之后换行。输出一组代表这个点的序号整数之后,请换行。
本题有多组数据。
输入数据数量不固定,但是介于3到14组之间。
对于每组数据:
每一行三个整数 n,m,k。 代表这一行对应的点到固定点的距离。
直至输入"over"。
输出每行包含一组代表点的数,数量不定,但介于1个到5个之间。
例子:(举例不是最优解)
输入:
1 3 9
2 4 6
235 63 26
200 30 200
152 16 46
28 94 56
1 3 9
2 4 6
235 63 26
200 30 200
152 16 46
28 94 56
0 255 255
over
输出:
1 2 7 8 13
4 5 6 9
3 10 11 12