OI题库

问题描述：

一位信使来到一个村落送信，他的送信方式是从某户X1出发，经过X2, X3, …, Xn-1最后到达Xn，X1…Xn为1..n的一种排列。即信使所走的路径为一条链，每户村民都恰好经过一次。这个村落中共有n户村民，第i(1≤i≤n)户村民可以用一个二元坐标(xi,yi)来表示其位置。信使刚刚拿到了村落的地图，但还不知道具体的任务细节，因此他想请你帮他算一下他每次送信可能走的最长路径，同时为了安慰信使，请你把最短路径也告诉他。

这是一道提交答案题目，你可以下载输入文件postman1.in…postman10.in，提交时只需提交相对应的输出文件postman1.out…postman10.out。

输入格式：

输入文件共有n+1行：

第一行是一个整数n，表示村落中共有n户村民。

第2到第n+1行每行两个整数xi和yi，表示第i户村民的坐标。

输出格式：

输出文件共两行，每行n个整数，为1..n的一种排列，分别表示信使可能走的最长路径和最短路径。

输入样例(postmanc.in)

4

0 0

0 4

3 0

3 4

输出样例(postmanc.out)

1 4 3 2

1 3 4 2

评分标准：

评测插件会首先检验你的输出是否合法，若不合法该测试点得0分。若输出路径合法，记标准输出的最长和最短路径长度分别为A、B，选手输出的最长和最短路径长度分别为C、D，则评分标准如下：

C≥A且D≤B 得10分

C≥0.90A且D≤1.10B得9分

C≥0.81A且D≤1.21B得8分

C≥0.73A且D≤1.33B得7分

C≥0.66A且D≤1.46B得6分

C≥0.59A且D≤1.61B得5分

C≥0.53A且D≤1.77B得4分

C≥0.48A且D≤1.95B得3分

C≥0.43A且D≤2.14B得2分

C>0且D<∞得1分

数据规模：
见数据。