UVA ACM (10012)

/*
 *******************************************************************************
 *
 * Filename: 10012.cpp
 *
 * Description: Just only use exhaustive search. It is not the fastest,
 *              but it's OK.
 *
 * Version: 0.1
 * Created: 4/20/2009 8:25:44 AM
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;


void find_result(vector<float>& circle_list, int l, int m);
float result = 0;
float calc(vector<float>& circle_list);
__inline float calc_two_circle(float c1, float c2);
__inline void swap(vector<float>& circle_list, int k, int m);

int main(int argc, char **argv)
{
    int case_num = 0;

    cin >> case_num;

    for (case_num; case_num != 0; case_num--) {
        int circle_num = 0;
        cin >> circle_num;
        vector<float> circle_list;
        for (int i = 0; i < circle_num; i++) {
            float r = 0;
            cin >> r;
            circle_list.push_back(r);
        }
        find_result(circle_list, 0, circle_num-1);
        cout.setf(ios::fixed);
        cout << setprecision(3) << result << endl;
        result = 0;
    }
}

/*
 *******************************************************************************
 * Find final result recursivly through all
 * permutations.
 *******************************************************************************
 */
void find_result(vector<float>& circle_list, int l, int m)
{
    if (l > m) {
        float width = calc(circle_list);
        if (result == 0 || result > width) {
            result = width;
        }
    } else {
        for(int i = l; i <= m; i++) {
            swap(circle_list, l, i);
            find_result(circle_list, l + 1, m);
            swap(circle_list, l, i);
        }
    }
}

/*
 *******************************************************************************
 * Calculate the width of a permutation.
 * Return:
 * return the width of the permutation.
 *******************************************************************************
 */
float calc(vector<float>& circle_list)
{
    int size = circle_list.size();
    vector<float> center_list(size, 0.0);
    center_list[0] = circle_list[0];
    float width = center_list[0] + circle_list[0];
    for (int i = 1; i < size; i++) {
        float center_pos = circle_list[i];
        for (int j = 0; j < i; j++) {
            float tmp_pos = center_list[j] + calc_two_circle(circle_list[j], circle_list[i]);
            if (tmp_pos > center_pos) {
                center_pos = tmp_pos;
            }
        }
        center_list[i] = center_pos;
        if (center_list[i] + circle_list[i] > width) {
            width = center_list[i] + circle_list[i];
        }
    }

    return width;
}

/*
 *******************************************************************************
 * Calculate the width between the center of the two circles.
 *******************************************************************************
 */
__inline float calc_two_circle(float c1, float c2)
{
    return sqrt(pow(c1+c2,2) - pow(abs(c1-c2),2));
}

/*
 *******************************************************************************
 * Swap two element k and m in a float vector.
 *******************************************************************************
 */
__inline void swap(vector<float>& circle_list, int k, int m)
{
    float tmp = circle_list[k];
    circle_list[k] = circle_list[m];
    circle_list[m] = tmp;
}