#P8083. 「COCI 2015.11」DRŽAVA

    ID: 7176 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-二分答案鸽巢原理均匀网格空间划分普通并查集0/1 背包位并行动态规划哈希表平方距离比较2015COCI

「COCI 2015.11」DRŽAVA

题目描述

一个遥远的国家刚刚举行了选举,新首相当选了。目前,这个国家没有一条公路,所以首相决定用双向公路把国内的城市连接起来,组成县,使国家现代化。

这个国家共有 NN 个城市,每个县由一个或多个城市组成,两个城市将位于同一个县,当且仅当使用新建的道路可以从一个城市到达另一个城市。这些城市在二维坐标系中用点来表示,两个城市之间的道路表示为连接两个城市所在点的线段。这条路的长度等于以公里为单位的线段的长度。

该国目前正遭受经济衰退,因此首相决定,由于缺乏预算,他们将不修建超过 DD 公里的道路。此外,如果至少有一个县存在一个非空的城市子集(可以包括该县的所有城市),使所选城市的居民总数能被 KK 整除,首相就会高兴。这里所选城市之间的路径可以经过同一个县内未被选中的城市。例如,如果 K=4K=4,一个县的城市分别有 3、5、7 个居民,首相就会高兴,因为前两个城市的居民总数等于 8。

请你确定最小的 DD 来帮助首相降低成本,使得首相感到高兴。

输入格式

第一行包含两个整数 N,KN,K。

接下来 NN 行,每行三个整数 xi,yi,kix_i,y_i,k_i,分别表示这个城市的坐标和这个城市的人口。

保证任意两座城市的坐标不同,每座城市的居民数均不能被 KK 整除,且一定存在使首相满意的方案。

输出格式

一行一个实数,表示最小的 DD,四舍五入保留三位小数。

3 3
0 4 4
1 5 1
2 6 1
1.414

只有当所有城市都在同一个县里首相才能高兴,所以最小的 DD 为 1.4141.414。

6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10
5.657

当前五个城市都在同一个县里首相才能高兴,且此时 DD 是最小的,所以最小的 DD 为 5.6575.657。

6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3
2.000

数据范围与提示

  • 对于 40%40\% 的数据,1≤N≤1031\le N\le10^3;
  • 对于 100%100\% 的数据,$1\le N\le5\times10^4,1\le K\le30,0\le x_i,y_i,k_i\le10^8$。