题目大意&题解
给你n个点,每个点都有一个高度h和一个位置\((x,y)\),每两个点的距离是欧几里得距离,每两个点之间的代价是高度差,问你把这n个点连起来,要求总代价除以总长度最小。
可以构造这样一个式子 \[ \frac{\sum cost_i}{\sum len_i}=ans \]
其中ans是最终的解(最小比率)。
通过移项: \[ \sum (cost_i-ans·len_i )=0 \]
我们发现,如果我们取得ans偏小,该式就大于0否则就会小于零,于是我们考虑到二分答案,然后从取小边(这里思考为什么要取小的边?)