[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$ 行来描述跳跃星门,每行两个正整数 $u_i,v_i$,表示有一个连接着行星系 $u_i$ 和 $v_i$ 的跳跃星门。注意这个连接是无向的。不会存在自己连向自己的情况。也不会存在重复连接的情况。接下来的一行,有一个正整数 $Q$,表示花花需要计算的非可疑度的行星对数。接下来的 $Q$ 行,每行两个正整数 $s_i,t_i$,表示花花需要计算从 $s_i$ 到 $t_i$ 的非可疑度。

输出格式


总共 $Q$ 行,每一行一个实数,表示花花第 $i$ 次需要计算的答案。你的答案需要和标准答案的差不超过 $0.01$ 才能得分。

输入输出样例

输入样例 #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

输出样例 #1

0.66667 
0.00000 
1.67544

说明

#### 简要题意(by yummy) 在边数不超过结点数的简单无权无向连通图内,每个结点在平面直角坐标系内对应一个坐标。有 $Q$ 组询问,每次给一对结点,找出一条路径,并找出一条直线,使得该路径上结点对应的坐标到直线距离平方和最小,并输出最小值。 [spj 0.01]