SRM503 Div1 Medium(500) KingdomXCitiesandVillages

TopCoder

KingdomXCitiesandVillages

道路の総延長の平均はそれぞれの村から伸ばす道路の平均長の和と等しい。村から伸ばす道路の長さは村を選ぶ順番によって決まる。村iから村jに道路を延ばすような村の選択の順番は何通りあるかと考える。

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

double dist( int x1, int y1, int x2, int y2 )
{ return sqrt(double(x1-x2)*(x1-x2)+double(y1-y2)*(y1-y2)); }

class KingdomXCitiesandVillages{public:
double determineLength( vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY )
{
    int N = (int)cityX.size();
    int M = (int)villageX.size();

    //  階乗
    double f[100];
    f[0] = 1;
    for ( int i=1; i<100; i++ )
        f[i] = f[i-1]*i;

    double ans = 0;

    for ( int i=0; i<M; i++ )
    {
        //  街への最短距離
        double dc = 1e10;
        for ( int j=0; j<N; j++ )
            dc = min( dc, dist(villageX[i],villageY[i],cityX[j],cityY[j]) );

        //  自身以外の村への距離
        vector<double> dv;
        for ( int j=0; j<M; j++ )
        if ( j != i )
            dv.push_back( dist(villageX[i],villageY[i],villageX[j],villageY[j]) );
        sort( dv.begin(), dv.end() );

        //  村iが最初に選ばれる
        ans += dc * f[M-1];

        for ( int j=0; j<M-1; j++ )
        {
            //  j番目に近い村が選ばれる
            for ( int k=1; k<=M-1; k++ )    //  村iの前にk個の村が選択
            if ( M-j-1 >= k )
                ans += min(dv[j],dc) * f[M-j-2]/f[M-j-2-(k-1)]/f[k-1]*f[k] * f[M-k-1];
        }
    }

    return ans / f[M];
}};