唉，看到这题直接想起自己的Day1，还是挺难受的，挺傻一题考试的时候怎么就没弄出来呢……
这两天CP让我给他写个题解，弄了不是很久就把这个题给弄出来了，真不知道考试的时候在干嘛。
明天就出发去北京了，祝自己APIO顺利吧。
/**************************************************************
Problem: 3528
User: zhuohan123
Language: C++
Result: Accepted
Time:1736 ms
Memory:25408 kb
****************************************************************/ #include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps=1e-;
inline int getnum()
{
int ans=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh*=-;ch=getchar();}
while(ch>=''&&ch<='')ans=ans*+ch-'',ch=getchar();
return fh*ans;
}
struct info
{
int n,x,y,x2,y2,xy;
info(){n=x=y=x2=y2=xy=;}
info(int X,int Y){n=;x=X;y=Y;x2=X*X;y2=Y*Y;xy=X*Y;}
info(int N,int X,int Y,int X2,int Y2,int XY){n=N;x=X;y=Y;x2=X2;y2=Y2;xy=XY;}
inline friend info operator+(info a,info b){return info(a.n+b.n,a.x+b.x,a.y+b.y,a.x2+b.x2,a.y2+b.y2,a.xy+b.xy);}
inline friend info operator-(info a,info b){return info(a.n-b.n,a.x-b.x,a.y-b.y,a.x2-b.x2,a.y2-b.y2,a.xy-b.xy);}
inline info operator+=(info b){n+=b.n;x+=b.x;y+=b.y;x2+=b.x2;y2+=b.y2;xy+=b.xy;return *this;}
inline double xbar(){return (double)x/(double)n;}
inline double ybar(){return (double)y/(double)n;}
inline double A(){return x2-*xbar()*x+n*xbar()*xbar();}
inline double B(){return *ybar()*x+*xbar()*y-*xy-*n*xbar()*ybar();}
inline double C(){return y2-*ybar()*y+n*ybar()*ybar();}
inline double delta()
{
if(n==)return ;
double a=A(),b=B(),c=C(),d=sqrt(a*a+b*b+c*c-*a*c);
double ans1=(a+c+d)/,ans2=(a+c-d)/;
if(ans1>ans2)swap(ans1,ans2);
return ans1>-eps?ans1:ans2;
}
};
int n,m;
struct point
{
int head,f[],deep,incir,wt;
info x;
}p[];
struct edge{int next,to;}g[];int gnum;
void addedge(int from,int to)
{
g[++gnum].to=to;g[gnum].next=p[from].head;p[from].head=gnum;
g[++gnum].to=from;g[gnum].next=p[to].head;p[to].head=gnum;
}
namespace Tree
{
void dfs(int po)
{
p[po].deep=p[p[po].f[]].deep+;
for(int i=;i<=;i++)
p[po].f[i]=p[p[po].f[i-]].f[i-];
for(int i=p[po].head;i;i=g[i].next)
if(g[i].to!=p[po].f[])
{
p[g[i].to].x+=p[po].x;
p[g[i].to].f[]=po;
dfs(g[i].to);
}
}
inline int lca(int u,int v)
{
if(p[u].deep>p[v].deep)swap(u,v);
for(int i=;i>=;i--)
if(p[p[v].f[i]].deep>=p[u].deep)v=p[v].f[i];
if(u==v)return u;
for(int i=;i>=;i--)
if(p[v].f[i]!=p[u].f[i])v=p[v].f[i],u=p[u].f[i];
return p[v].f[];
}
void solve()
{
dfs();
int q=getnum();
while(q--)
{
int u=getnum(),v=getnum(),l=lca(u,v);
printf("%.5lf\n",(p[u].x+p[v].x-p[l].x-p[p[l].f[]].x).delta()+eps);
}
}
}
namespace Circle
{
bool ins[];
int s[],sr;
int cir[],cnum;
info cinfo[];
inline info cirwalk(int l,int r){return cinfo[r]-cinfo[l-];}
bool dfscir(int po,int from)
{
ins[s[++sr]=po]=true;
for(int i=p[po].head;i;i=g[i].next)
if(g[i].to!=from)
{
if(ins[g[i].to])
{
while(s[sr]!=g[i].to)
{
cir[++cnum]=s[sr];
p[s[sr]].incir=cnum;
sr--;
}
cir[++cnum]=g[i].to;
p[g[i].to].incir=cnum;
return true;
}
else if(dfscir(g[i].to,po))return true;
}
sr--;
ins[po]=false;return false;
}
void dfstree(int po,int wt)
{
p[po].wt=wt;
p[po].deep=p[p[po].f[]].deep+;
for(int i=;i<=;i++)
p[po].f[i]=p[p[po].f[i-]].f[i-];
for(int i=p[po].head;i;i=g[i].next)
if(g[i].to!=p[po].f[]&&!p[g[i].to].incir)
{
p[g[i].to].x+=p[po].x;
p[g[i].to].f[]=po;
dfstree(g[i].to,wt);
}
}
inline int lca(int u,int v)
{
if(p[u].deep>p[v].deep)swap(u,v);
for(int i=;i>=;i--)
if(p[p[v].f[i]].deep>=p[u].deep)v=p[v].f[i];
if(u==v)return u;
for(int i=;i>=;i--)
if(p[v].f[i]!=p[u].f[i])v=p[v].f[i],u=p[u].f[i];
return p[v].f[];
}
void solve()
{
dfscir(,);
for(int i=;i<=cnum;i++)dfstree(cir[i],cir[i]);
for(int i=;i<=cnum;i++)cir[i+cnum]=cir[i];
for(int i=;i<=*cnum;i++)cinfo[i]=cinfo[i-]+p[cir[i]].x;
int q=getnum();
while(q--)
{
int u=getnum(),v=getnum();
if(p[u].wt==p[v].wt)
{
int l=lca(u,v);
printf("%.5lf\n",(p[u].x+p[v].x-p[l].x-p[p[l].f[]].x).delta()+eps);
}
else
{
int fu=p[u].wt,fv=p[v].wt;
info iu=p[u].x-p[fu].x,iv=p[v].x-p[fv].x;
if(p[fu].incir>p[fv].incir)swap(fu,fv);
info imid1=cirwalk(p[fu].incir,p[fv].incir);
info imid2=cirwalk(p[fv].incir,p[fu].incir+cnum);
printf("%.5lf\n",min((iu+imid1+iv).delta(),(iu+imid2+iv).delta())+eps);
}
}
}
}
int main(int argc, char *argv[])
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=getnum(),m=getnum();
for(int i=;i<=n;i++)
{
int x=getnum(),y=getnum();
p[i].x=info(x,y);
}
for(int i=;i<=m;i++)addedge(getnum(),getnum());
if(m==n-)Tree::solve();
else Circle::solve();
return ;
}