SRM579 Div1 Hard(1000) MarblePositioning

TopCoder

MarblePositioning

ビー玉の個数が高々8個なので、全ての並び順を試してみれば良い。半径aと半径bのビー玉が接する距離は√((a+b)2-(a-b)2)。

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

class MarblePositioning{public:
double totalWidth( vector <int> radius )
{
    int n = (int)radius.size();
    double ans = 1e100;

    sort(radius.begin(),radius.end());
    do
    {
        vector<double> p(n);
        for ( int i=0; i<n; i++ )
        for ( int j=0; j<i; j++ )
        {
            double d = sqrt(
                pow(radius[i]+radius[j],2.) -
                pow(radius[i]-radius[j],2.) );
            p[i] = max( p[i], p[j]+d );
        }
        ans = min( ans, p[n-1] );
    }
    while (next_permutation(radius.begin(),radius.end()));

    return ans;
}};