#3975. [WF2012]Asteroid Rangers

这是2112年，人类已经征服了太阳系。太空游侠队已经在任何大块岩石上建立了基地（即使不适宜居住）。你作为小行星通讯部门的一员，工作是确保所有太空游侠小行星基地都能尽可能廉价地与其他小行星基地交流。你可以建立从每个基地到另外所有基地的直接交流连接，但那可能过分昂贵。相反，你想要建立最少数量的连接从而每个人都可以发送信息给其他所有人，信息可能通过一个或多个基地中转。建立任何连接的费用与它连接的两个基地之间的（欧几里德）距离成比例，所以这个问题看起来不怎么难。

但这只是一个小小的困难。小行星有一个运动的趋势，所以两个当前很接近的基地在将来不一定还是很接近。因此随着时间流逝，你一定会乐意转换你的交流连接，从而在任何时候你都拥有最廉价的中继系统。转换这些连接花费时间和金钱，所以你对于了解将要执行多少次转换很感兴趣。

一些假设让这个任务更简单。每个小行星可以视为一个点。小行星总是以固定的速度沿直线运动。没有小行星会和其他小行星相撞。此外，任何在时刻t(t≥0)变得最优的中继系统在任何时刻s(s满足t<s<t+10^-6)时是独一无二最优的。初始最优的中继系统也是独一无二的。