BOJ 28297 - 차량 모듈 제작

BOJ 28297 - 차량 모듈 제작

기하 문제이다.

모든 원 쌍을 $O(n^2)$에 검사하여 접하거나 $d < r_1+r_2$ 라면 DSU로 먼저 이어두자.

그렇지 않다면 두 원끼리 필요한 곡선의 길이를 그래프의 간선으로 두고 MST를 구성해줄 수 있다.

double PI = acos(-1);
double len(int x1, int y1, int r1, int x2, int y2, int r2) {
   if (r1 < r2) swap(x1, x2), swap(y1, y2), swap(r1, r2);
   double dx = abs(x1 - x2);
   double dy = abs(y1 - y2);
   double d = sqrt(dx * dx + dy * dy);

   double theta = acos((r1 - r2) / d);

   double ret = 0;

   double h = d * sin(theta);

   ret += h * 2;
   ret += 2 * PI * r2 * (theta / PI);
   ret += 2 * PI * r1 * ((2 * PI - 2 * theta) / (2 * PI));

   return ret;
}
struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n;
   cin >> n;
   vector<array<int, 3>> a(n);
   vector<tuple<double, int, int>> edges;
   DSU dsu(n);
   for (auto &[x, y, r]: a) cin >> x >> y >> r;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {

         int dx = a[i][0] - a[j][0];
         int dy = a[i][1] - a[j][1];
         int rsum = a[i][2] + a[j][2];
         if (ll(dx) * dx + ll(dy) * dy <= ll(rsum) * rsum) {
            dsu.merge(i, j);
            debug(i, j);
            continue;
         }

         edges.pb({len(a[i][0], a[i][1], a[i][2], a[j][0], a[j][1], a[j][2]), i, j});
      }
   }
   sort(all(edges));
   double ans = 0;
   for (auto &[w, i, j]: edges) {
      if (!dsu.is_merged(i, j)) {
         debug(w, i, j);
         dsu.merge(i, j);
         ans += w;
      }
   }
   cout << setprecision(15) << fixed << ans;
}