7528: BZOJ3528：[Zjoi2014]星系调查

 银河历59451年，在银河系有许许多多已被人类殖民的星系。如果想要在行

星系间往来，大家一般使用连接两个行星系的跳跃星门。  一个跳跃星门可以把 物质在它所连接的两个行星系中互相传送。 露露、花花和萱萱被银河系星际联盟调查局任命调查商业巨擘ZeusLeague+ 的不正当商业行为。 在银河系有N个已被ZeusLeague+成功打入市场的行星系，不妨标号为 1,2,...,N。而ZeusLeague+在这N个行星系之间还拥有自己的M个跳跃星门。使 用这些跳跃星门，ZeusLeague+的物资就可以在这N个行星系中两两任意互相传 输。由于经费问题，跳跃星门的个数不会超过行星系的个数。 露露在颇费周折之后得到了ZeusLeague+在这N个行星系中的各自的贸易总 额C[i]。 萱萱设计了一个经济学特征指标D[i]来度量这N个行星系的经济学特征。于 是，我们可以用二元组(C[i],D[i])来表示第i个行星系的XP(Xuan's Position)。现 在假设我们有k个行星系的XPs，把它们放置在二维平面上，然后我们用一条直 线去拟合这些XPs。定义一条直线与XPs的相斥度为这条直线到各个XP的Euclid 距离的平方之和。再令XPs的线性假设相斥度为所有直线与XPs的相斥度中的 最小者。那么，这个值越小，ZeusLeague+在这k个行星系中的相互贸易活动就 越可疑，从而值得进一步调查。花花负责计算许多行星系对(u,v)的非可疑度。一 条跳跃星门航线的非可疑度被定义为它经过的所有行星系（包括起点和终点）的 XPs的线性假设相斥度。而一个行星系对(u,v)的非可疑度则被定义为所有以u为 起点，v为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指 从某个行星系开始，通过跳跃星门依次到达某些行星系，然后终止，并且中途不 重复经过行星系，这样的一个过程。 花花负责计算许多行星系对(u,v)的非可疑度。一条跳跃星门航线的非可疑度 被定义为它经过的所有行星系（包括起点和终点）的XPs的线性假设相斥度。 而一个行星系对(u,v)的非可疑度则被定义为所有以u为起点，v为终点的跳跃星 门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始，通过 跳跃星门依次到达某些行星系，然后终止，并且中途不重复经过行星系，这样的 一个过程。 在花花数天夜以继日的工作之后，平行调查组的你——大名鼎鼎的计算机科 学家Hcceleration.Gerk.Gounce不忍心看到她这样不眠不休，于是你在完成了手 头的工作之后决定帮一帮她。

---

输入格式

 第一行是N，M，分别表示这个银河系内的行星系的个数

以及跳跃星门的个数。 接下来N行，每行2个正整数C[i], D[i]，表示第i 个行星系的XP(Xuan's Position)。 接下来的M行来描述跳跃星门，每行2个正整数u[i],v[i]，表示有一个连接 着行星系u[i]和v[i]的跳跃星门。注意这个连接是无向的。不会存在自己连向自 己的情况。也不会存在重复连接的情况。 接下来的一行，有一个正整数Q，表示花花需要计算的非可疑度的行星对数。 接下来的Q行，每行2个正整数s[i], t[i]，表示花花需要计算从s[i]到t[i]的 非可疑度。

---

输出格式

总共Q行，每一行一个实数，表示花花第i次需要计算的答

案。你的答案需要和标准答案的差不超过0.01才能得分。

---

样例输入

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

---

提示

没有写明提示

---

题目来源

没有写明来源