#P3528. [Zjoi2014]星系调查
[Zjoi2014]星系调查
[ZJOI2014] 星系调查
题目描述
银河历 年,人类已在许多行星系建立殖民地,在行星系之间可以经由双向跳跃星门运送物资。星际联盟调查局任命露露、花花和萱萱调查商业巨擘 ZeusLeague+。该公司进入了编号为 到 的行星系市场,并拥有 座跳跃星门。任意两个行星系可以经由这些星门互达,且 。
露露取得了第 个行星系的贸易总额 ,萱萱为它计算了经济指标 。将 看作该行星系在平面上的一个点,称为 XP。给定若干行星系,一条直线与这些 XP 的相斥度,是每个 XP 到这条直线的欧氏距离的平方之和。对所有直线取最小值,得到这组 XP 的线性假设相斥度。该数值越小,公司在这些行星系间的贸易活动就越可疑。
一条从 到 的航线由相邻星门连接的行星系组成。航线不能重复经过行星系。该航线的非可疑度是它经过的所有行星系的 XP 的线性假设相斥度,包含起点和终点。行星系对 的非可疑度,是所有从 到 的航线的非可疑度最小值。
花花需要查询许多行星系对,请帮助她计算答案。
输入格式
第一行有两个整数 ,表示行星系数及星门数。接下来 行,每行两个整数 ,表示行星系 的 XP。
随后 行,每行两个整数 ,表示一座连接这两个行星系的双向星门。没有自环和重边。
接下来一行一个整数 ,表示查询数。随后 行,每行两个整数 ,询问这一对行星系的非可疑度。
输出格式
输出 行,每行一个实数,依次表示每次查询的答案。与参考答案的绝对误差不得超过 。
样例 #1
6 6
3 4
5 6
1 3
4 4
3 3
2 4
1 2
1 3
2 3
2 4
3 5
5 6
3
3 6
2 4
4 6
0.66667
0.00000
1.67544
数据范围
,,。所有星门端点和查询端点都属于 到 。
| 原赛测试点 | 上限 | 上限 | 条件 |
|---|---|---|---|
| 1 | ,图是一条链 | ||
| 2 | |||
| 3 | |||
| 4–5 | |||
| 6 | |||
| 7 | ,图是一个环 | ||
| 8–10 | |||