几何加简单最短路。
题意是给出若干圆的圆心以及半径，求出从给出的起点到终点的最短路径的长度，可以移动的区域是圆覆盖到的任意一个位置。
做法是这样的，对圆两两求交点，用这些得到的交点以及起点和终点作为我们要构造的图的顶点。因为我们要的是最短路径，所以如果我们要从一个区域穿越到另一区域的时候，必然是经过这些交点的。然后我们可以对这些交点两两判断是否能够相互到达。这个判断才是这道题的关键。判断的方法可以有几种，我想到的一是先求出直线与所有圆的交点，排序以后判断所有的圆能否覆盖掉这条线段；而我的是另一种方法，就是用一个队列，将还没有被覆盖的线段存在队列里，每次跟圆相交判断线段是否仍未被覆盖。
最后来一个单源最短路就搞掂了！
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue> using namespace std; const double EPS = 1e-;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
bool operator < (Point a) const { return sgn(x - a.x) < || sgn(x - a.x) == && y < a.y;}
bool operator <= (Point a) const { return (sgn(x - a.x) < || sgn(x - a.x) == && sgn(y - a.y) < ) || (sgn(x - a.x) == && sgn(y - a.y) == );}
bool operator == (Point a) const { return sgn(x - a.x) == && sgn(y - a.y) == ;}
void print() { cout << x << '~' << y << endl;}
} ;
template <class T> T sqr(T x) { return x * x;}
typedef Point Vec;
Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);} inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
inline double angle(Vec v) { return atan2(v.y, v.x);}
inline double angle(Vec a, Vec b) { return acos(dotDet(a, b) / vecLen(a) / vecLen(b));}
inline Vec vecUnit(Vec x) { return x / vecLen(x);}
inline Vec rotate(Vec x, double rad) { return Vec(x.x * cos(rad) - x.y * sin(rad), x.x * sin(rad) + x.y * cos(rad));}
inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);} struct Line {
Point s, t;
Line() {}
Line(Point s, Point t) : s(s), t(t) {}
Vec vec() { return t - s;}
Point point(double x) { return s + vec() * x;}
} ;
typedef Line Seg; inline bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(a - x, b - x)) == && sgn(dotDet(a - x, b - x)) < ;}
inline bool onSeg(Point x, Seg s) { return onSeg(x, s.s, s.t);} inline Point lineIntersect(Point P, Vec v, Point Q, Vec w) { return P + v * (crossDet(w, P - Q) / crossDet(v, w));}
inline Point lineIntersect(Line a, Line b) { return lineIntersect(a.s, a.vec(), b.s, b.vec());} struct Circle {
Point c;
double r;
Circle() {}
Circle(Point c, double r) : c(c), r(r) {}
Point point(double a) { return Point(c.x + cos(a) * r, c.y + sin(a) * r);}
} ;
int lineCircleIntersect(Line L, Circle C, vector<Point> &sol) {
Vec nor = normal(L.vec());
Point mid = lineIntersect(C.c, nor, L.s, L.vec());
double len = sqr(C.r) - sqr(vecLen(C.c - mid));
if (sgn(len) < ) return ;
if (sgn(len) == ) { sol.push_back(mid); return ;}
Vec dis = vecUnit(L.vec());
len = sqrt(len);
sol.push_back(mid + dis * len);
sol.push_back(mid - dis * len);
return ;
} int circleCircleIntersect(Circle C1, Circle C2, vector<Point> &sol) {
double d = vecLen(C1.c - C2.c);
if (sgn(d) == ) {
if (sgn(C1.r - C2.r) == ) return -;
return - + (C1.r > C2.r);
}
if (sgn(C1.r + C2.r - d) < ) return ;
if (sgn(fabs(C1.r - C2.r) - d) > ) return - + (C1.r > C2.r);
double a = angle(C2.c - C1.c);
double da = acos((sqr(C1.r) + sqr(d) - sqr(C2.r)) / (2.0 * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.push_back(p1);
// p1.print();
if (p1 == p2) return ;
sol.push_back(p2);
// p2.print();
return ;
} inline bool ptInCircle(Point p, Circle c) { return sgn(vecLen(c.c - p) - c.r) <= ;} const int N = ;
Circle dev[N];
vector<Point> vex;
int sid, tid;
double mat[N * N][N * N]; Seg qseg[N * N]; double cal(int pi, int pj, int n) {
// queue<Seg> seg;
vector<Point> ip;
int qh, qt;
qh = qt = ;
// while (!seg.empty()) seg.pop();
if (vex[pj] < vex[pi]) swap(pi, pj);
Seg L = Seg(vex[pi], vex[pj]);
// seg.push(L);
qseg[qt++] = L;
for (int i = ; i < n; i++) {
// int sz = seg.size();
int sz = qt - qh;
for (int j = ; j < sz; j++) {
// Seg tmp = seg.front();
// seg.pop();
Seg tmp = qseg[qh++];
// if (pi == 0 && pj == 2) {
// tmp.s.print();
// tmp.t.print();
// puts("tmp");
// }
ip.clear();
if (lineCircleIntersect(L, dev[i], ip) == ) {
if (ip[] < ip[]) swap(ip[], ip[]);
// if (pi == 0 && pj == 4) {
// ip[0].print();
// ip[1].print();
// puts("ip");
// }
if (ip[] <= tmp.s || tmp.t <= ip[])
// seg.push(tmp);
qseg[qt++] = tmp;
else if (tmp.s <= ip[] && ip[] <= tmp.t) {
if (vecLen(tmp.s - ip[]) > EPS)
// seg.push(Seg(tmp.s, ip[0]));
qseg[qt++] = Seg(tmp.s, ip[]);
if (vecLen(tmp.t - ip[]) > EPS)
// seg.push(Seg(ip[1], tmp.t));
qseg[qt++] = Seg(ip[], tmp.t);
} else if (tmp.s < ip[] && ip[] <= tmp.t && sgn(vecLen(tmp.s - ip[])))
// seg.push(Seg(tmp.s, ip[0]));
qseg[qt++] = Seg(tmp.s, ip[]);
else if (tmp.s <= ip[] && ip[] < tmp.t && sgn(vecLen(ip[] - tmp.t)))
// seg.push(Seg(ip[1], tmp.t));
qseg[qt++] = Seg(ip[], tmp.t);
} else
// seg.push(tmp);
qseg[qt++] = tmp;
}
// if (seg.size() == 0)
if (qh == qt)
return vecLen(vex[pi] - vex[pj]);
}
return -1.0;
} void PRE(int n) {
vex.clear();
for (int i = ; i < n; i++) {
cin >> dev[i].c.x >> dev[i].c.y >> dev[i].r;
// vex.push_back(dev[i].c);
}
vex.push_back(dev[].c);
vex.push_back(dev[n - ].c);
Point ps = dev[].c, pt = dev[n - ].c;
for (int i = ; i < n; i++) {
for (int j = ; j < i; j++) {
// cout << i << " = = " << j << endl;
circleCircleIntersect(dev[i], dev[j], vex);
}
}
sort(vex.begin(), vex.end());
int t = (int) (unique(vex.begin(), vex.end()) - vex.begin());
while (vex.size() > t) vex.pop_back();
// cout << "size " << vex.size() << endl;
for (int i = , sz = vex.size(); i < sz; i++) {
if (vex[i] == ps) sid = i;
if (vex[i] == pt) tid = i;
for (int j = ; j <= i; j++) {
if (i == j) mat[i][j] = 0.0;
else mat[i][j] = mat[j][i] = cal(i, j, n);
}
}
// cout << sid << ' ' << tid << endl;
// for (int i = 0, sz = vex.size(); i < sz; i++) {
// vex[i].print();
// for (int j = 0; j < sz; j++) printf("%7.4f ", mat[i][j]);
// cout << endl;
// }
} const double FINF = 1e100;
double dis[N * N];
int q[N * N << ];
double spfa() {
int sz = vex.size();
// queue<int> Q;
// while (!Q.empty()) Q.pop();
int qh, qt;
qh = qt = ;
for (int i = ; i < sz; i++) dis[i] = FINF;
dis[sid] = 0.0;
// Q.push(sid);
q[qt++] = sid;
// while (!Q.empty()) {
while (qh < qt) {
// int cur = Q.front();
// Q.pop();
int cur = q[qh++];
for (int i = ; i < sz; i++) {
if (mat[cur][i] < ) continue;
if (dis[i] > dis[cur] + mat[cur][i]) {
dis[i] = dis[cur] + mat[cur][i];
// Q.push(i);
q[qt++] = i;
}
}
}
// for (int i = 0; i < sz; i++) cout << dis[i] << ' '; cout << endl;
return dis[tid];
} int main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
int T, n;
cin >> T;
for (int cas = ; cas <= T; cas++) {
cin >> n;
PRE(n);
printf("Case %d: ", cas);
double ans = spfa();
if (ans < FINF) printf("%.4f\n", ans);
else puts("No such path.");
}
return ;
}
附加自己出的数据：
8
2
0 0 1
2 0 1
2
0 0 1
4 1 2
3
-3 0 2
0 2 2
3 0 2
3
-3 0 2
0 3 3
3 0 2
6
-6 0 2
-3 0 2
0 3 3
3 0 2
7 0 2
0 8 2
10
-6 0 2
-3 0 2
0 3 3
3 0 2
7 0 2
0 8 2
-4 8 2
-8 8 2
-7 2 2
-8 4 2
3
0 10 7
-1 -1 100
10 0 7
3
-3 0 2
0 3 3
3 0 2
——written by Lyon