#2131. 投影

投影

投影

题目描述

第二试投影(projection) IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 投影(projection) 【问题描述】 换一个角度看,世界可能就不同。—— 小强 k 维空间中有n 个黑点与n 个白点。我们为每一个黑点确定一个互不相同的对应的 白点,这样一共有n! 种对应方法。我们定义这n 个黑点与n 个白点之间的‘‘移动距离’’ 为,在所有的对应方法中,对应的黑点与白点之间的n 个.欧.几.里.德距离的和的.最.小.值。 例如: 考虑一维中的三个黑点{1,5,6} 与三个白点{2,3,4},那么它们之间的移动距 离为: |1−2|+|5−3|+|6−4| = 4。你可以验证一下这确实是距离和最小的一种对应方法。 你得到了三维空间中的n 个黑点与n 个白点。你想把它们投影到一个k(1 ≤k ≤2) 维子空间上。一维子空间就是三维空间中的一条直线,二维子空间则是三维空间中的 一个平面。一个点在一个子空间中的投影点就是这个子空间中距离它最近的点。例如, (0, 0, 0), (1, 1, 0), (1, 0, 0), (0, 1, 0) 这四个点投影到x −y = 0,z = 0 这条直线上之后,得 到的投影点是(0, 0, 0), (1, 1, 0), (0.5, 0.5, 0), (0.5, 0.5, 0)。 你希望这n 个黑点和n 个白点投影到这个k 维子空间之后的移动距离.最.大。请你 计算这个最大值除以n。 【输入格式】 从文件projection.in 中读入数据。 每个测试文件中可能有多个测试用例,每个测试用例的格式如下: 第一行两个数n 和k,表示点数以及降到的维度。 后面2n 行,每行三个数,表示点的坐标。 文件最后有一行包含两个数−1 −1。 【输出格式】 输出到文件projection.out 中。 对文件中的每个测试用例,输出一行一个数(长度不要超过30),表示结果。 你的答案与参考答案的.相.对.误.差不超过10−7 时被认为是正确的。 只有一个文件中所有的测试用例的结果都是正确的才能获得这个测试文件所对应 的分数。 【样例1 输入】 2 1 0 0 0 1 1 0 第7 页 共8 页 第二试投影(projection) IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 0 1 0 1 0 0 -1 -1 【样例1 输出】 0.70710678118655 【样例2 输入】 4 2 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 -1 -1 【样例2 输出】 0.73883404559321 【样例3】 见选手目录下的projection/projection3.in 与projection/projection3.ans。 【数据规模】 对于30% 的数据,k = 1,n ≤1000, 所有的点的z 都是0。一个文件中最多包含一 个测试用例。 对于另外40% 的数据,k = 1,n ≤1000,所有的点的坐标都是[−1, 1] 之间均匀独 立随机生成的,一个文件中最多包含十个测试用例。 对于另外30% 的数据,k = 2,n ≤20,所有的点的坐标都是[−1, 1] 之间均匀独立 随机生成的,一个文件中最多包含十个测试用例。 对于100% 的数据,点的坐标的范围都是−1 到+1 之间的,答案不小于0.01。 第8 页 共8 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1
0 0 0
1 1 0
0 1 0
1 0 0
-1 -1
0.70710678118655

样例 2

4 2
0 0 0
0 1 1
1 0 1
1 1 0
0 0 1
0 1 0
1 0 0
1 1 1
-1 -1
0.73883404559321