[C++] 차량 모듈 제작 (백준 28297번)

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

 

모든 기어 쌍에 대해서 벨트의 길이의 구하고 (총 n*n번) 그 길이들을 가지고 최소 스패닝 트리를 만들면 된다.

 

하나의 기어 쌍에 대한 벨트의 길이를 구하는 과정은 다음과 같다.

 

두 중심 사이의 거리를 빗변(h)으로 하고 두 반지름의 차이를 높이(a)로 하는 삼각형을 생각해보자. 피타고라스 정리에 의해 밑변(b)도 구할 수 있고 arcsin을 통해 α도 구할 수 있다. α를 활용하여 두 호의 길이도 구할 수 있다.

벨트의 길이는 밑변 * 2 + 왼쪽 원의 호 + 오른쪽 원의 호 이다.

 

주의할 점은!!! (PI + 2α)는 항상 더 큰 반지름과 곱해져야 하고 (PI - 2α)는 항상 더 작은 반지름과 곱해져야 한다는 것이다. 이것 때문에 몇시간을 고생했는데.. 대지호님께서 그 지옥에서 꺼내주었다 ㅜ.ㅜ

 

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

double PI = acos(-1);
vector<int> parent;

int find(int a) {
    if (parent[a] == a) return a;
    else return parent[a] = find(parent[a]);
}

bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
        return true;
    } else {
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<tuple<double, double, double>> gear; // {x, y, r}
    for (int i = 0; i < n; i++) {
        double x, y, r;
        cin >> x >> y >> r;
        gear.push_back({x, y, r});
    }

    vector<tuple<double, int, int>> e; // {w, u, v}
    for (int i = 0; i < n; i++) {
        auto [x1, y1, r1] = gear[i];
        for (int j = i + 1; j < n; j++) {
            auto [x2, y2, r2] = gear[j];
            double a = abs(r1 - r2);
            double h = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
            if (h <= r1 + r2) {
                e.push_back({0, i, j});
            } else {
                double b = sqrt(h * h - a * a);
                double alpha = asin(a / h);
                double c1, c2;
                if (r1 >= r2) {
                    c1 = r1 * (PI + 2 * alpha);
                    c2 = r2 * (PI - 2 * alpha);
                } else {
                    c1 = r2 * (PI + 2 * alpha);
                    c2 = r1 * (PI - 2 * alpha);
                }
                e.push_back({2 * b + c1 + c2, i, j});
            }
        }
    }

    int en = e.size();
    sort(e.begin(), e.end());

    parent = vector<int>(n);
    for (int i = 0; i < n; i++) parent[i] = i;

    int cnt = 0;
    double ans = 0;
    for (auto [w, u, v]: e) {
        if (unite(u, v)) {
            cnt++;
            ans += w;
        }
        if (cnt == n - 1) break;
    }

    cout << fixed;
    cout.precision(10);
    
    cout << ans << '\n';
}

(AC)