当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

4892:Defence of the Trees

Special Judge 特殊评判
题目描述
There are n trees (each of them can be considered as a point) on a two-dimensional coordinate system. There are k categories of trees, category of the ith tree are represented by Ai. There are also m stumps (each of them can be considered as a point, too) on this two-dimensional coordinate system. Stumps can be connected with straight wires.

Your task is to connect some of the stumps by wires to build exactly one simple polygon (that is, a polygon without self-intersection and degeneration) which contains trees of all k categories inside. Meanwhile, in order to save money, you should make the total length of wires as short as possible. Your task is to calculate the shortest total length of wires, or to determine that there is no solutions.
输入解释
There are several testcases, please process till EOF.

In each testcases:
First one line, three numbers n, m, k. Following n lines contains n 2D-coordinates describing each tree. Next one line contains n number, where ith number Ai denotes ith tree's category. Next m lines describe the coordinates of stumps, you may assume that there is no trees lying on segments between any two stumps.

All input will be integer, and absolute value of them will be less than 23333, 1 ≤ n ≤ 300, 1 ≤ m ≤ 40, 1 ≤ k ≤ 6,1 ≤ Ai ≤ k.In about 90% of testcases,m ≤ 10.
输出解释
For each testcase, print one line, if there is no solutions, Output "Impossible" (without quotes), else output a real number indicating the minimal total length. Your answer will be considered correct if and only if the absolute error or relative error are less than 10-6.
输入样例
2 4 1  
0 0  
2 0  
1 1  
1 -1  
1 1  
-3 -1  
5 1  
2 4 2  
0 0  
2 0  
1 2  
1 -1  
1 1  
-3 -1  
5 1  
输出样例
10.472135955000  
16.944271909999  
来自杭电HDUOJ的附加信息
Author Fudan University
Recommend

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-4892

最后修改于 2020-10-25T23:17:51+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
20000/10000MS(Java/Others) 65536/65536K(Java/Others)