Codeforces 1059D
题意：给你平面上一些点，你需要找出一个与直线$y=0$相切的圆使得包含所有点。
彻头彻尾的数学题……
显然如果$y$有正有负就不能构造圆使得与$y=0$相切。
考虑二分半径，然后验证答案。
观察可得，与直线$y=0$相切的圆圆心一定在$y=b$上，也就是圆的纵坐标
我们可以尝试枚举所有点，然后在$y=b$上找到一个范围使得在当前半径下都能覆盖这个点，然后取交集即可。
点$(x,y)$范围相当于解圆不等式$(x-a)^2+(y-r)^2 \leq r^2$，我们解得$a=x±\sqrt{2rt-y^2}$，因为这个不等式是关于$a$的一元二次不等式，二次项系数为正，所以我们取$[x-\sqrt{2rt-y^2},x+\sqrt{2rt-y^2}]$，这个就是范围。
注意二分的范围，也就是最大可能半径的计算：
考虑极端情况$(-10^7, 1), (10^7, 1)$，我们过这两点作圆，将这两点连线后再与圆心形成三角形，根据$(r-1)^2+(10^7)^2=r^2$，可解得$r=\frac{10^{14}+1}{2}$，那么这个就是最大的半径长。
还有就是注意还有可能圆心在$y=-b$上，类似地特判一下即可。如果开方里面是负的说明当前半径无解
知识点：1、浮点数比较
2、二分范围千万不要想当然
3、这种几何题和数学相关，也和二分/三分相关
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MAXN = 100000 + 5, LOGS = 17, INF = 300000000000005ll;
struct edge {LL u, v, d;};
struct data {
LL u, d;
bool operator < (const data &b) const {return d > b.d;}
};
std::vector<edge > G[MAXN];
std::set<std::pair<LL, LL> > nt;
std::priority_queue<data > q;
LL n, m, Q, vis[MAXN], dep[MAXN], pre[MAXN][30], h[MAXN], dis[50][MAXN];
void dfs(LL u, LL fa) {
dep[u] = dep[fa] + 1, vis[u] = 1, pre[u][0] = fa;
for (LL i = 1; i <= LOGS; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (LL i = 0; i < (LL)G[u].size(); i++) {
edge &e = G[u][i];
if (e.v != fa && !vis[e.v]) {
h[e.v] = h[u] + e.d;
dfs(e.v, u);
if (u < e.v) nt.erase(std::make_pair(u, e.v)); else nt.erase(std::make_pair(e.v, u));
}
}
}
void dij(LL st, LL d[MAXN]) {
for (LL i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
d[st] = 0, q.push((data){st, 0});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue; vis[p.u] = 1;
for (LL i = 0; i < (LL)G[p.u].size(); i++) {
edge &e = G[p.u][i];
if (d[e.v] > d[p.u] + e.d) d[e.v] = d[p.u] + e.d, q.push((data){e.v, d[e.v]});
}
}
}
LL LCA(LL a, LL b) {
if (dep[a] < dep[b]) std::swap(a, b);
for (LL i = LOGS; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (LL i = LOGS; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
LL getdist(LL u, LL v) {return h[u] + h[v] - 2 * h[LCA(u, v)];}
void clean() {
ms(h, 0), ms(vis, 0), ms(dep, 0);
}
int solve() {
clean();
for (LL u, v, d, i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &u, &v, &d);
G[u].push_back((edge){u, v, d}), G[v].push_back((edge){v, u, d});
if (u < v) nt.insert(std::make_pair(u, v)); else nt.insert(std::make_pair(v, u));
}
dfs(1, 0);
//for (LL i = 0; i < (LL)nt.size(); i++) printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
LL cnt = 0;
for (std::set<std::pair<LL, LL> >::iterator it = nt.begin(); it != nt.end(); it++) {
std::pair<LL, LL> e = *it;
LL &u = e.first, &v = e.second;
//printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
if (u > v) continue;
dij(u, dis[++cnt]);
}
//for (LL i = 1; i <= n; i++) for (LL j = 1; j <= n; j++) printf("i=%lld j=%lld lca=%lld\n", i, j, LCA(i, j));
scanf("%lld", &Q);
while (Q--) {
LL u, v; scanf("%lld%lld", &u, &v);
LL ans = getdist(u, v);
for (LL i = 1; i <= cnt; i++) {
ans = std::min(ans, dis[i][u] + dis[i][v]);
}
printf("%lld\n", ans);
}
return 0;
}
int main() {
scanf("%lld%lld", &n, &m), solve();
return 0;
}
