#P3528. [Zjoi2014]星系调查

    ID: 2739 传统题 1000ms 256MiB 尝试: 232 已通过: 120 难度: 8 上传者: 标签>难度分类提高+/省选-线性代数与代数二次型的特征值极值图论基环树拆环排序与序列处理一维前缀和树算法LCA树链剖分CF2400

[Zjoi2014]星系调查

[ZJOI2014] 星系调查

题目描述

银河历 5945159451 年,人类已在许多行星系建立殖民地,在行星系之间可以经由双向跳跃星门运送物资。星际联盟调查局任命露露、花花和萱萱调查商业巨擘 ZeusLeague+。该公司进入了编号为 11 到 NN 的行星系市场,并拥有 MM 座跳跃星门。任意两个行星系可以经由这些星门互达,且 M≤NM\le N。

露露取得了第 ii 个行星系的贸易总额 CiC_i,萱萱为它计算了经济指标 DiD_i。将 (Ci,Di)(C_i,D_i) 看作该行星系在平面上的一个点,称为 XP。给定若干行星系,一条直线与这些 XP 的相斥度,是每个 XP 到这条直线的欧氏距离的平方之和。对所有直线取最小值,得到这组 XP 的线性假设相斥度。该数值越小,公司在这些行星系间的贸易活动就越可疑。

一条从 uu 到 vv 的航线由相邻星门连接的行星系组成。航线不能重复经过行星系。该航线的非可疑度是它经过的所有行星系的 XP 的线性假设相斥度,包含起点和终点。行星系对 (u,v)(u,v) 的非可疑度,是所有从 uu 到 vv 的航线的非可疑度最小值。

花花需要查询许多行星系对,请帮助她计算答案。

输入格式

第一行有两个整数 N,MN,M,表示行星系数及星门数。接下来 NN 行,每行两个整数 Ci,DiC_i,D_i,表示行星系 ii 的 XP。

随后 MM 行,每行两个整数 ui,viu_i,v_i,表示一座连接这两个行星系的双向星门。没有自环和重边。

接下来一行一个整数 QQ,表示查询数。随后 QQ 行,每行两个整数 si,tis_i,t_i,询问这一对行星系的非可疑度。

输出格式

输出 QQ 行,每行一个实数,依次表示每次查询的答案。与参考答案的绝对误差不得超过 0.010.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
0.66667
0.00000
1.67544

数据范围

1≤N,Q≤1051\le N,Q\le10^5,N−1≤M≤NN-1\le M\le N,0≤Ci,Di≤970\le C_i,D_i\le97。所有星门端点和查询端点都属于 11 到 NN。

原赛测试点 NN 上限 QQ 上限 条件
1 1010 M=N−1M=N-1,图是一条链
2 5050
3 100100 M=N−1M=N-1
4–5 100000100000
6 1010 M=NM=N
7 5050 M=NM=N,图是一个环
8–10 100000100000 M=NM=N