백준 13433 기하 문제

https://www.acmicpc.net/problem/13433

13433번: 기하 문제

풀이 

두 개의 원이 접해있다면 다음과 같은 그림처럼 표현됩니다.

원의 중심 사이에는 다음과 같은 삼각형이 생길 것이고 

 

피타고라스를 이용한다면 삼각형의 세 개의 변을 구할 수 있습니다.

 

 

 삼각형에서 나온 값을 토대로 다음 원의 중심 좌표를 알 수 있습니다.

 

 

이제 우리에게 주어진 문제는 원을 어떤 순서로 배치해야 가장왼쪽점과 가장오른쪽점의 거리가 가장 짧은지인데...

 

다행히 문제에서 나오는 원의 개수는 N (3 ≤ N ≤ 8)이기 때문에

8! = 40,320의 경우의 수로 배치를 해볼 수 있습니다.

저는 next_permutation을 사용해서 모든 배치의 경우의 수를 탐색하도록 구현했습니다.

 

 

 

 

 

한 가지 주의해야 할 점이 있습니다!!

 

 

다음 그림과 같이 원이 이전에 설치된 원이 아닌 다른 원에 접하는 경우가 생길 수가 있기 때문에

다른 원과 접하는 경우도 고려해서 원의 중심을 구해야됩니다.

 

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

using namespace std;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cout << fixed;
    cout.precision(10);

    vector<float> arr;
    vector<float> r;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        arr.push_back(i);
    for (int i = 0; i < n; i++)
    {
        float a;
        cin >> a;
        r.push_back(a);
    }

    float ans = 1000000000000;

    do
    {
        vector<float> P;
        P.push_back(0);

        for (int i = 1; i < n; i++)
        {
            float nextR = r[arr[i]];
            float tempP = P[0];
            for (int j = 0; j < P.size(); j++)
            {
                float nowR = r[arr[j]];
                float addX = 2 * sqrt(nowR * nextR);

                tempP = max(tempP,P[j]+ addX);
            }

            P.push_back(tempP);
        }

        ans = min(P.back(), ans);
    }
    while (next_permutation(arr.begin(), arr.end()));

    cout << ans << endl;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.