원 (JUNGOL 1255)

https://jungol.co.kr/problem/1255

---

아이디어

가능한 모든 순서로 배열해봅시다. 하나의 배열이 정해지면 가능한 최소의 직사각형의 크기를 어떻게 구할 수 있을까요?

 

첫번째 원의 중심의 x좌표를 0이라고 해봅시다. i번째 원의 중심의 x좌표는 max(j번째 원의 중심의 x좌표+(i번째 원과 j번째 원 사이의 x좌표의 차))로 나타낼 수 있습니다. 이때 i번째 원과 j번째 원 사이의 x좌표의 차는 두 원의 반지름을 알고있으므로 피타고라스의 정리를 사용해주면 sqrt(4*(j번째 원의 반지름)*(i번째 원의 반지름))이 됩니다. 마지막에 직사각형의 크기는 max(i번째 원의 x좌표+반지름)-min(i번째 원의 x좌표-반지름)를 해주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

ll N;
vector <double> R;
vector <double> v;
bool ck[11]={0};

double res=2e9;
void solve()
{
    double Min=-R[v[0]],Max=R[v[0]];
    double loc[11]={0};

    for (ll i=1;i<N;i++)
    {
        for (ll j=0;j<i;j++)
            loc[i]=max(loc[i],loc[j]+sqrt(4*R[v[j]]*R[v[i]]));
        Min=min(Min,loc[i]-R[v[i]]);
        Max=max(Max,loc[i]+R[v[i]]);
    }

    res=min(res,Max-Min);
}

void track()
{
    if (v.size()==N) solve();
    else
    {
        for (ll i=0;i<N;i++)
        {
            if (ck[i]) continue;
            ck[i]=true;
            v.push_back(i);
            track();
            v.pop_back();
            ck[i]=false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll i;
    double x;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>x;
        R.push_back(x);
    }

    track();

    cout<<fixed; cout.precision(3);
    cout<<res;
}