网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
约翰的电网
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | fence3.in | 输出文件 | fence3.out |
USACO/fence3(译 by Felicia Crazy)
描述
农夫约翰已经决定建造电网。他已经把他的农田围成一些奇怪的形状,现在必须找出安放电源的最佳位置。
对于段电网都必须从电源拉出一条电线。电线可以穿过其他电网或者跨过其他电线。电线能够以任意角度铺设,从电源连接到一段电网的任意一点上(也就是,这段电网的端点上或者在其之间的任意一点上)。这里所说的“一段电网”指的是呈一条线段状的电网,并不是连在一起的几段电网。若几段电网连在一起,那么也要分别给这些电网提供电力。
已知所有的 F(1 <= F <= 150)段电网的位置(电网总是和坐标轴平行,并且端点的坐标总是整数,0 <= X,Y <= 100)。你的程序要计算连接电源和每段电网所需的电线的最小总长度,还有电源的最佳坐标。
电源的最佳坐标可能在农夫约翰的农田中的任何一个位置,并不一是整数。
PROGRAM NAME: fence3
INPUT FORMAT (file fence3.in)
第一行包括 F ——电网的数量。
下面的 F 行每行包括两个 X,Y 对,表示这段电网的两个端点。
OUTPUT FORMAT(file fence3.out)
只有一行,输出三个浮点数,每个保留一位小数,相邻两个之间留一个空格。假定你的电脑的输出库会正确地对小数进行四舍五入。
这三个数是:
- 电源最佳坐标的 X 值,
- 电源最佳坐标的 Y 值,和
- 需要的电线的总长度(要最小)。
SAMPLE INPUT (file fence3.in)
30 0 0 1
2 0 2 1
0 3 2 3
SAMPLE OUTPUT (file fence3.out)
1.0 1.6 3.7