HBC22977清明梦超能力者黄YY,线段树,树,数据结构电网题解

一沫阳光 算法基础篇 57 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
农夫约翰已经决定建造电网,他已经把他的农田围成一些奇怪的形状,现在必须找出安放电源的最佳位置, 对于段电网都必须从电源拉出一条电线,电线可以穿过其他电网或者跨过其他电线,电线能够以任意角度铺设,从电源连接到一段电网的任意一点上,这里所说的“一段电网”指的是呈一条线段状的电网,并不是连在一起的几段电网,若几段电网连在一起,那么也要分别给这些电网提供电力, 已知所有的F(1

农夫约翰已经决定建造电网。他已经把他的农田围成一些奇怪的形状,现在必须找出安放电源的最佳位置。 对于段电网都必须从电源拉出一条电线。电线可以穿过其他电网或者跨过其他电线。电线能够以任意角度铺设,从电源连接到一段电网的任意一点上(也就是,这段电网的端点上或者在其之间的任意一点上)。这里所说的“一段电网”指的是呈一条线段状的电网,并不是连在一起的几段电网。若几段电网连在一起,那么也要分别给这些电网提供电力。 已知所有的F(1 <= F <= 150)段电网的位置(电网总是和坐标轴平行,并且端点的坐标总是整数,0 <= X,Y <= 100)。你的程序要计算连接电源和每段电网所需的电线的最小总长度,还有电源的最佳坐标。 电源的最佳坐标可能在农夫约翰的农田中的任何一个位置,并不一是整数

HBC22977清明梦超能力者黄YY,线段树,树,数据结构电网题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC22977清明梦超能力者黄YY 线段树 数据结构电网题解