背景

男主:咱们去街头涂鸦把?

女主:好啊好啊~就去***吧~【自行脑补】

(他们来到了***)

男主:啊嘞?这是什么奇怪的图案?有个坐标系,还有好多点?

女主:看,旁边有说明。嗯……“如果分数能达到最大值,将获得一份神秘大礼。”……

男主:这个……看起来好难的样子啊……

描述

    原来,墙上画的是一个平面直角坐标系以及n个点。旁边的说明上写道:请用n-1条直线来连接这n个点,使得任意两点之间能直接或间接地连接起来。连接的每条直线都能获得一定分数,若设两短点为A、B,则这条直线AB的分数定义为A、B两点之间的距离,A、B两点的两坐标值之差的绝对值之和(即|xA-xB|+|yA-yB|)以及向量OA与向量OB的点积(O为坐标原点)的值这三者的平均数。如果分数达到最大值,就能拿到一份神秘大礼。

    男主很想在女神面前炫耀一番,拿到这份神秘大礼,于是悄悄地记录下了这个图案并发给了你,请你帮助他。

输入格式

    第一行,一个数n。

    接下来的n行,第i+1行为编号为i的点的坐标xi、yi。坐标均保留8位小数。

输出格式

    第一行为一个数,表示能获得的最高分。要求与标准答案的差值不大于10-4。标准输出保留17位小数。(本题设有SpecialJudge)

    接下来的n-1行,每行输出连接的一条直线的两端点的编号。若有多种可行方案,输出其中一种即可。输出顺序不做要求

样例输入

4
0.00000000 0.00000000
2.50000000 2.50000000
4.10000000 4.10000000
1.00000000 1.00000000

样例输出

19.58169311629441400
3 2
4 3
3 1

数据范围与约定

对于30%的数据,保证0<n≤100。

对于50%的数据,保证0<n≤1000。

对于70%的数据,保证0<n≤3000。

对于100%的数据,保证0<|xi|,|yi|≤100000,0<n≤5000。

来源

轩轩醉了