#include <iostream>
#include <bits/stdc++.h>
#include <graphics.h> // Include the EasyX header file
#include <conio.h>
#include <windows.h>
using namespace std; // Add this line to use std namespace
void circle(int x, int y, int radius);//画无填充的圆。
int n; // 圆的个数
float a[100]; //圆的半径
float a_x[100];//初始圆的横坐标
float x[100];//计算当前圆排列坐标
float minn = 100000;
void Compute() {
float w = 0;
int i = 0;
float temp = 0;
for (i = 0; i < n; i++)
{
temp = x[i] + a[i];
if (w < temp)
{
w = temp;
}
}
//w = x[n-1]+a[n-1];
if (w < minn)
{
minn = w;
}
cout << "min=" << w << endl;
}
void Print(float b[100]) {
Sleep(500);
cleardevice();
setlinestyle(PS_SOLID, 3);
setlinecolor(RED);//线的颜色为红色
float temp = 0;
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
//temp = (x[i] * 20) + b[0] * 20;
temp = x[i] * 20;
circle((int)b[i] * 20, (int)temp, (int)b[i] * 20);
}
//Sleep(500);
cout << endl;
}
float Center(int t) {//求圆心坐标:假定它跟前面的所有圆相切，求出圆心坐标，值最大的就是符合条件的。
float ans = a[t];
for (int i = 0; i < t; i++) {
float v = x[i] + 2.0*sqrt(a[t] * a[i]);//2.0*sqrt(a*b)=sqrt(pow(a+b,2),pow(a-b,2))
//float v = x[i - 1] + 2.0*sqrt(a[t] * a[i]);//2.0*sqrt(a*b)=sqrt(pow(a+b,2),pow(a-b,2))
if (v > ans) ans = v;
}
return ans;
}
void Swap(float &a, float &b) {
float t = a; a = b; b = t;
}
//排列树
void BackTrack(int t) { //第t个顶点
if (t >= n) {//到达叶结点
Compute();
Print(a);
return;
}
else {
for (int i = t; i < n; i++) {//不断交换剩下的圆的位置。
Swap(a[t], a[i]);
float centerx = Center(t);//求t的圆心坐标
if (t == 0)
{
centerx = a[0];
}
if (centerx + a[t] < minn) {
x[t] = centerx;
BackTrack(t + 1);
}
Swap(a[t], a[i]);
}
}
}
int main()
{
float temp = 0;
memset(a, 0, sizeof(a));
memset(a_x, 0, sizeof(a_x));
memset(x, 0, sizeof(x));
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
initgraph(960, 960);
setlinestyle(PS_SOLID, 3);
setlinecolor(RED);//线的颜色为红色
for (int i = 0; i < n; i++)
{
a_x[i] = a[i] + temp;
temp = temp + 2 * a[i];
circle((int)(a[i] * 20), (int)(a_x[i] * 20), (int)(a[i] * 20));
x[i] = a_x[i];
}
BackTrack(0);
cout << "minn=" << minn << endl;
_getch();
closegraph();
return 0;
}
