AOJ2402 天の川

解法

---

星の変な入力を頑張って5辺にしてDijkstra。

ソース

---

typedef pair< double , int > Pi;
bool used[100];
double info[100][100];
int n, m, l;
L stars[100][5];
 
void add( int x, int y, int a, int r, const int z){
  G hosi(5);
  for(int i = 0 ; i < 5 ; i++ ){
    double theta = Degree_to_Radian(a + 72 * i);
    double nx = r * sin( theta ), ny = r * cos( theta );
    hosi[i] = P( x - nx, y + ny);
  }
  for(int i = 0 ; i < 5 ; i++ ){
    stars[z][i] = L( hosi[i * 2 % 5], hosi[(i + 1) * 2 % 5]);
  }
}
double dist( LLL a, LLL b){
  double ret = INF;
  for(int i = 0 ; i < a.size() ; i++ ){
    for(int j = 0 ; j < b.size() ; j++ ){
      ret = min( ret, distancion( a[i], b[i]));
    }
  }
  return ret;
}
double Dijkstra(){
  priority_queue< Pi , vector< Pi > , greater< Pi > > que;
  fill_n( used, 100, false);
  que.push( Pi( 0.0, m));
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.sc == l) return p.fr;
    if(used[p.sc]++) continue;
    for(int i = 0 ; i < n ; i++ )
      que.push( Pi( info[p.sc][i] + p.fr, i));
  }
}
  
int main(){
  while(cin >> n >> m >> l, l){
    m--, l--;
    for(int i = 0 ; i < n ; i++ ){
      int x, y, a, r;
      cin >> x >> y >> a >> r;
      add( x, y, a, r, i);
    }
  
    for(int i = 0 ; i < n ; i++ ){
      for(int j = i + 1 ; j < n ; j++ ){
        double dist = INF;
        for(int a = 0 ; a < 5 ; a++ ){
          for(int b = 0 ; b < 5 ; b++ ){
            dist = min( dist, distancion( stars[i][a], stars[j][b]));
          }
        }
        info[i][j] = info[j][i] = dist;
      }
    }
    cout << fixed << setprecision(10) << Dijkstra() << endl;
  }
}