seuOJ465 - 距离和最小

题目描述

Quoi? Vous avez dit que la réponse à la question était en décimales. Ne soyez pas drôle. Impossible. La réponse à la question doit être un nombre entier.

DingDing 所在的地区是一个二维平面。在这个二维平面上有 nn 个村庄，第 ii 个村庄位于 (pi,0)(p_i,0)，有 aia_i 个居民。其中政府将为这 nn 个村庄修建 k(k≤n)k(k \le n) 个医院，医院可以建设在坐标系上的任意位置。请你找到一种修建医院的方式，使得每个村庄的每个人到达最近的一所医院的欧几里得距离的和最小，输出这个最小距离和。

形式化的来说，假如你把 kk 所医院建在 (x1,y1),(x2,y2),…,(xk,yk)(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)，你需要最小化 ∑i=1nai×min⁡j=1k(pi−xj)2+(yj)2\sum_{i=1}^{n} a_i \times \min\limits_{j=1}^{k} \sqrt{(p_i-x_j)^2+(y_j)^2} 。

假设你输出的答案为 oufouf，标准答案为 ansans，你的答案会被认为正确当且仅当 ∣ans−ouf∣max⁡(1,ans)≤10−6\frac{|ans-ouf|}{\max(1,ans)}\le 10^{-6}。

评测时你的答案将和四舍五入保留到小数点后 1515 位的标准答案比较。

让我们来回忆一下什么是欧几里得距离，欧几里得距离为两点间最短距离，即两点所连接而形成线段的长度，假如在二维平面上有两个点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2)，那么这两点之间的欧几里得距离为 (x1−x2)2+(y1−y2)2\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}。

输入格式

第一行，一个整数 t(1≤t≤100)t(1\le t \le 100) ，代表数据组数。

对于每组数据：
第一行，两个整数 n,k(1≤k≤n≤2000)n,k(1\le k \le n \le 2000) 代表村庄数与设置的医院数。
接下来连续的 nn 行，每行两个整数 p,a(1≤p≤106;1≤a≤106)p,a(1\le p \le 10^6;1\le a \le 10^6)，代表村庄位于 (p,0)(p,0) 与村庄人口数为 aa，保证所有的 pp 互不相同。

对于同一测试点内的所有数据，保证 ∑n≤2000\sum n \le 2000 。

输出格式

对于每组数据，输出一行答案代表每个村庄的每个人到达最近的一所医院的距离和最小值。

样例

输入样例

3
2 1 
1 1000000 
1000000 1000000 
1 1 
1 1
5 2
1 2
3 1
4 5
7 2
8 6

输出样例

999999000000.000000 
0.000000
9.000000

提示
在样例的第 11 组数据中，我们可以把医院建在 (520.1314,0)(520.1314,0) 处。