ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1183 Chain-Confined Path

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1183&lang=jp


・概要
複数の円が与えられ、それらが1つずつ繋がっていて鎖状になっています。
最初の円の中心の座標から、最後の円の中心の座標までの最短距離を求める問題です。
制約等は省略。


・解法
幾何の処理 + ワーシャルフロイドで解くことができます。

円と円の交点を求め、交点間の距離を求めます。
あとは交点を結んだ直線が円の外側にないかどうかを判定しつつ、距離を求め直して、あとはワーシャルフロイドで最短距離をだすことができます。


ソースコード
※ライブラリは省略

#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)

static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
typedef complex<double> Point; 

//円
struct Circle{
   Point p;
   double r;
   Circle(){}
   Circle(Point p, double r):p(p),r(r){}
};

int n;
Circle c[100];
double dist[200][200];
Point point[200];

void warshall_floyd(){
   for(int k = 0 ; k < 2*n ; k++){
      for(int i = 0 ; i < 2*n ; i++){
	 for(int j = 0 ; j < 2*n ; j++){
	    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
	 }
      }
   }
}

double solve(){
   rep(i,200)rep(j,200)dist[i][j] = (i==j) ? 0 : INF;
   
   //交点を求める
   point[0] = c[0].p;
   point[2*n-1] = c[n-1].p;
   for(int i = 1 ; i < n ; i++){
      vector<Point> tmp = getCrossPointCC(c[i],c[i-1]);
      point[2*i-1] = tmp[0];
      point[2*i] = tmp[1];
   }
   
   //各点間の距離を求める
   for(int i = 0 ; i < 2*n ; i++){
      for(int j = i+1 ; j < 2*n ; j++){
	 dist[i][j] = dist[j][i] = abs(point[i]-point[j]);
      }
   }
   
   //交差判定
   for(int i = 0 ; i < 2*n ; i++){
      for(int j = i+1 ; j < 2*n ; j++){
	 bool flag = true;
	 for(int k = ((i%2==0) ? i+1 : i+2) ; k <= ((j%2==0) ? j-2 : j-1) ; k+=2){
	    if(!intersectSS(point[i],point[j],point[k],point[k+1]))flag = false;
	    if(!flag)break;
	 }
	 if(!flag)dist[i][j] = dist[j][i] = INF;
      }
   }

   warshall_floyd();

   return dist[0][2*n-1];
}

int main(){
   while(cin >> n){
      if(n==0)break;

      rep(i,n){
	 Point p;
	 double r;
	 cin >> p.real() >> p.imag() >> r;
	 c[i] = Circle(p,r);
      }
      
      printf("%.10f\n",solve());
   }
   return 0;
}