Codeforces School Team Contest #2 D. Hyperdrive

Codeforces

Hyperdrive

惑星を２つ経由する距離の最小値の半分。平方根の計算が重いので、なるべく減らすようにしたら通った。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

double dist( vector<int> a, vector<int> b )
{
    return sqrt( pow((double)a[0]-b[0],2) +
                 pow((double)a[1]-b[1],2) +
                 pow((double)a[2]-b[2],2) );
}

int main()
{
    int n;  cin >> n;
    vector<vector<int> > v( n, vector<int>( 3 ) );
    for ( int i=0; i<n; i++ )
        cin >> v[i][0] >> v[i][1] >> v[i][2];

    vector<double> d;
    for ( int i=0; i<n; i++ )
        d.push_back( dist(v[0],v[i]) );

    double ans = 1e100;
    for ( int i=1; i<n; i++ )
    for ( int j=i+1; j<n; j++ )
        if ( d[i]+d[j] <= ans )
            ans = min( ans, d[i]+dist(v[i],v[j])+d[j] );

    cout.precision( 20 );
    cout << ans/2 << endl;
}