ICPC 国内予選2012E 鎖中経路 AOJ1183
パッと見DP感があるな～と思って少し考えたらほんとにDPだった。
解説：
i番目の円とi+1番目の円の交点は2つある。その二つの交点に適当に0個目、1個目の点とすると。
dp[i][j] =0番目の円（一番端の円）から、 i番目の円とi+1番目のj(=0,1)個目の交点にたどり着くまでの最小の長さ
と定義できて、それを典型的なDPで回せば求まる。
if(0~iの0,1個目の交点から今の点までの線分が、任意の円に重なっている場合) dp[i][j] = min( dp[0~i][0,1] + （0~iの0,1個目の交点から今の点までの距離） )
で求められる。
if文の判定は線分の交差判定をぶん回せばよい
dist関数の引数をint型にするという珍プレーをして無限に時間を消費したので気を付けていきたい（まあライブラリを使えばこういうミスはないと思うが、）
#include <bits/stdc++.h> using namespace std; #define EPS (1e-10) #define equals(a, b) (fabs((a) - (b)) < EPS) struct Point{ double x, y; Point(double x = 0, double y = 0): x(x), y(y) {} Point operator + (Point p) { return Point(x + p.x, y + p.y); } Point operator - (Point p) { return Point(x - p.x, y - p.y); } Point operator * (double a) { return Point(a * x, a * y); } Point operator / (double a) { return Point(x / a, y / a); } double norm() {return x * x + y * y; } double abs() {return sqrt(norm()); } bool operator < (const Point &p) const{ return (x != p.x ? x < p.x : y < p.y); } bool operator == (const Point &p) const{ return (fabs(x - p.x) < EPS && fabs(y - p.y) < EPS); } }; typedef Point Vector; struct Circle{ Point c; double r; Circle(Point c = Point(), double r = 0.0): c(c), r(r) {} }; double norm(Vector a){ return a.x * a.x + a.y * a.y; } double abs(Vector a){ return sqrt(norm(a)); } double arg(Vector p){ return atan2(p.y, p.x); } Vector polar(double a, double r){ return Point(cos(r) * a, sin(r) * a); } pair<Point, Point> getCrossPoints(Circle c1, Circle c2){ double d = abs(c1.c - c2.c); double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d)); double t = arg(c2.c - c1.c); return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)); } int n; double dist(double x1,double y1,double x2,double y2){ return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ); } bool judgeIenter(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy) { double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax); double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx); double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx); double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx); // return (tc * td < 0 && ta * tb < 0); //端点を含まない場合 return (tc * td <= 0 && ta * tb <= 0); // 端点を含む場合 } double INF = 10000000; double dp[110][2]; double d[110][3]; double p[110][2][2]; bool check(int a,int aa,int b,int bb){ double ax,ay,bx,by; if(a == -1){ ax = d[0][0]; ay = d[0][1]; }else{ ax = p[a][aa][0]; ay = p[a][aa][1]; } if(b == n-1){ bx = d[n-1][0]; by = d[n-1][1]; }else{ bx = p[b][bb][0]; by = p[b][bb][1]; } bool flag = true; for(int i = max(0,a);i < b;i++){ if(judgeIenter(ax,ay,bx,by,p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]) == false){ flag = false; break; } } return (flag); } int main(){ while(true){ cin >> n; if(n == 0)break; for(int i = 0;i <= n+1;i++){ dp[i][0] = INF; dp[i][1] = INF; } for(int i = 0;i < n;i++){ for(int j = 0;j < 3;j++){ cin >> d[i][j]; } } for(int i = 0;i < n-1;i++){ Circle c1 = {Point(d[i][0], d[i][1]), d[i][2]}; Circle c2 = {Point(d[i+1][0], d[i+1][1]), d[i+1][2]}; pair<Point, Point> ansp = getCrossPoints(c1, c2); p[i][0][0] = ansp.first.x; p[i][0][1] = ansp.first.y; p[i][1][0] = ansp.second.x; p[i][1][1] = ansp.second.y; } for(int i = 0;i < 2;i++){ dp[0][i] = dist(d[0][0],d[0][1],p[0][i][0],p[0][i][1]); } for(int i = 1;i < n-1;i++){ for(int k = 0;k < 2;k++){ double nx = p[i][k][0],ny = p[i][k][1]; if(check(-1,0,i,k)) dp[i][k] = dist(d[0][0],d[0][1],nx,ny); for(int j = 0;j < i;j++){ for(int kk = 0;kk < 2;kk++){ if(check(j,kk,i,k))dp[i][k] = min(dp[i][k],dp[j][kk]+dist(p[j][kk][0],p[j][kk][1],nx,ny)); } } } } double ans = INF; for(int i = -1;i < n-1;i++){ for(int k = 0;k < 2;k++){ if(check(i,k,n-1,0)){ if(i == -1)ans = min(ans,dist(d[0][0],d[0][1],d[n-1][0],d[n-1][1])); else ans = min(ans,dp[i][k]+dist(p[i][k][0],p[i][k][1],d[n-1][0],d[n-1][1])); } } } printf("%lf\n",ans); } }
