做题时间：2022.10.5
\(【题目描述】\)
给定一个点数为 \(n(n\leq 4\times 10^5)\)，边数为 \(m(4\times 10^5)\) 的无向联通图，满足 \(m\leq n\)，对于第 \(i\) 个点，给定一个笛卡尔坐标系上的点 \((X_i,Y_i)\)，先有 \(Q(Q\leq 4\times 10^5)\) 次询问，每次询问给出图上两个不同的点 \(s_i,t_i\) ，对于每一条图上 \(s_i\) 到 \(t_i\) 的简单路径的所有点，求其线性假设相斥度最小值。（线性假设相斥度：对于一个点集，对于一条直线 \(l\)，这条直线与点集中所有点的欧几里得距离之和的最小可能值）
\(【输入格式】\)
第一行两个整数 \(n,m\)，表示点数和边数
接下来 \(n\) 行，每行两个整数表示 \(X_i,Y_i\)
接下来 \(m\) 行，每行两个整数 \(u,v\) 表示图中的一条边 \((u,v)\)
接下来一行一个整数 \(q\) 表示询问次数
接下来 \(q\) 行每行两个整数 \(s_i,t_i\) 表示询问
\(【输出格式】\)
输出共 \(q\) 行，对于每一个询问输出一行一个浮点数表示答案。要求绝对值误差不超过 \(10^{-4}\)
\(【考点】\)
数学、二次函数、基环树、差分
\(【做法】\)
初中奥数题
首先这种猎奇的询问没有什么较好的方法直接求，可以考虑化一下柿子。
可以知道点 \((x_i,y_i)\) 到直线 \(Ax+By=C\) 的距离公式为：
\[dis=\frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}} \]但是带入计算的时候肯定要消元，三个未知数不太好搞，可以用斜率柿子：
\[dis=\frac{|kx_i-y_i+b|}{\sqrt{k^2+1}} \]所以，要求的便是：
\[\begin{aligned} ans &=\sum\limits_{i=s_i}^{t_i}dis((x_i,y_i),l)^2 \\ &=\sum\limits_{i=s_i}^{t_i} \frac{(kx_i-y_i+b)^2}{k^2+1} \\ &= \frac{1}{k^2+1}(k^2\sum x_i^2-2k\sum x_iy_i +\sum y_i^2+2kb\sum x_i-2b\sum y_i +dis\times b^2) \end{aligned} \]的最小值。然后发现原式中包含了 \(k\) 和 \(b\) 两个未知数，先消掉一个。即，设 \(k\) 为常数，将与 \(b\) 有关的柿子：
\[dis\times b^2+2(k\sum x_i-\sum y_i)b \]变为最小值。这个柿子是个关于 \(b\) 的开口向上的二次函数，因此它取最小值时：
\[b=\frac{\sum y_i-k\sum x_i}{dis} \]令 \(\overline{y_i}=\frac{\sum y_i}{dis}\)，\(\overline{x_i}=\frac{\sum x_i}{dis}\)，将 \(b\) 带回原式，并将含 \(k\) 项整理，有：
\[\frac{k^2\sum(x_i^2-2x_i\overline{x}+\overline{x}^2)+k\sum (2x_i\overline{y}-2x_iy_i+2\overline{x}y_i-2\overline{x}\overline{y})+\sum(y_i^2-2y_i\overline{y}+\overline{y}^2)}{k^2+1} \]换元一下，令：
\[\begin{aligned} A&=\sum(x_i^2-2x_i\overline{x}+\overline{x}^2)\\ B&=\sum (2x_i\overline{y}-2x_iy_i+2\overline{x}y_i-2\overline{x}\overline{y})\\ C&=\sum(y_i^2-2y_i\overline{y}+\overline{y}^2) \end{aligned} \]原式可化为：
\[\frac{Ak^2+Bk+C}{k^2+1} \]（其中 \(A,B,C\) 为常数） 是不是很眼熟
像这种分数线上下均为关于相同未知数的二次函数，可以分离常数，也可以直接化成二次函数的形式用 \(\Delta\) 讨论，具体而言，令
\[t=\frac{Ak^2+Bk+C}{k^2+1} \]有：
\[tk^2+t=Ak^2+Bk+C \]\[(A-t)k^2+Bk+(C-t)=0 \]原式有解，有：
\[\begin{aligned} \Delta &=B^2-4(A-t)(C-t)\\ &=-4t^2+4(A+C)t+B^2-4AC\geq 0 \end{aligned} \]这个关于 \(t\) 的二次函数开口向下，又大于等于0，因此 \(t\) 的取值必须在与 \(x\) 轴的交点之间，即 \(t\in[\frac{-b-\sqrt{\Delta}}{2a},\frac{-b+\sqrt{\Delta}}{2a}]\) ，所以：
\[t_{min}=\frac{A+C-\sqrt{A^2+B^2+C^2-2AC}}{2} \]然后就可以 \(O(1)\) 求解力（喜
回到原题，\(m\leq n\) 意味着图为基环树或树，直接预处理 \(\sum x_i\) 等一堆东西即可。对于基环树而言将环找出来， 以环为主体 ，若询问两点在以环上某点为根的同一棵子树上，直接求解，否则将环上两种路径对应的解取个最小值就行了。
\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=5e5+50;
struct edge{
int to,nxt;
}a[N<<1];
struct point{
#define sumx(a) a.sumx
#define sumy(a) a.sumy
#define mulx(a) a.mulx
#define muly(a) a.muly
#define sumxy(a) a.sumxy
#define len(a) a.len
ll sumx,sumy,mulx,muly,sumxy,len;
void Insert(int a,int b)
{
sumx+=(ll)a,sumy+=(ll)b;
sumxy+=(ll)a*b,mulx+=(ll)a*a,muly+=(ll)b*b,len++;
}
double calc()
{
double A=mulx-1.0*(sumx*sumx)/len;
double B=-2*sumxy+2.0*sumx*sumy/len;
double C=muly-1.0*(sumy*sumy)/len;
return (A+C-sqrt(A*A+B*B+C*C-2*A*C))/2;
}
point operator +(const point a)
{
return (point){sumx(a)+sumx,sumy(a)+sumy,mulx(a)+mulx,
muly(a)+muly,sumxy(a)+sumxy,len(a)+len};
}
point operator -(const point &a)
{
return (point){sumx-sumx(a),sumy-sumy(a),mulx-mulx(a),
muly-muly(a),sumxy-sumxy(a),len-len(a)};
}
}sum[N],pre[N];
bool Is_cir[N];
int head[N],dep[N],col[N],f[N][25],fa[N];
int cir[N],x[N],y[N],pos[N],cnt,ed,n,m;
inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
inline bool Merge(int x,int y)
{
int X=Find(x),Y=Find(y);
if(X==Y) return true;
fa[X]=Y;
return false;
}
inline void dfs(int u,int fa,int c)
{
dep[u]=dep[fa]+1,col[u]=c,f[u][0]=fa;
pre[u]=pre[fa];
pre[u].Insert(x[u],y[u]);
for(int i=1;i<25;i++) f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].to;
if(v!=fa&&!Is_cir[v]) dfs(v,u,c);
}
}
inline bool Find_cir(int u,int fa,int st)
{
if(Is_cir[u]&&u!=st) return true;
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].to;
if(v!=fa&&!(Is_cir[u]&Is_cir[v])){
cir[++ed]=v;
if(!Find_cir(v,u,st)) ed--;
else return true;
}
}
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=24;i>=0;i--){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
}
if(x==y) return x;
for(int i=24;i>=0;i--){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
void add(int u,int v)
{
cnt++;
a[cnt].to=v;
a[cnt].nxt=head[u];
head[u]=cnt;
}
double solve(int x,int y)
{
int l=lca(x,y);
point now=pre[x]+pre[y]-pre[l]-pre[f[l][0]];
return now.calc();
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y),add(x,y),add(y,x);
if(Merge(x,y)) cir[++ed]=x,Is_cir[x]=Is_cir[y]=true;//并查集找环
}
if(m==n-1) dfs(1,0,0);
else{
Find_cir(cir[1],0,cir[1]);
for(int i=1;i<=ed;i++){
int now=cir[i];
pos[now]=i,Is_cir[now]=true;
sum[i]=sum[i-1],sum[i].Insert(x[now],y[now]);
}
for(int i=1;i<=ed;i++) dfs(cir[i],0,cir[i]);
}
int q;
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
if(m==n-1||col[x]==col[y]) printf("%lf\n",solve(x,y));//如果是一棵树或是基环树上同一子树内
else{
int posx=pos[col[x]],posy=pos[col[y]];
if(posx>posy) swap(posx,posy);
point now=pre[x]+pre[y]-pre[col[x]]-pre[col[y]];
point ans1=now+sum[posy]-sum[posx-1],ans2=now+sum[ed]+sum[posx]-sum[posy-1];
printf("%lf\n",min(ans1.calc(),ans2.calc()));
}
}
return 0;
}