UVa 11116 Babel Towers

题目描述

$\text{Babel Inc.}$ 设计了一种由圆形截面柱体堆叠而成的塔结构。每个柱体的高度为单位长度 $1$，半径为
r
k
r_k
rk​，材料均匀且不可变形。柱体从底部到顶部编号为 $0,1,\dots ,n-1$，其中柱体 $0$ 放置在地面上，柱体 $k$（$k\ge 1$）放置在柱体 $k-1$ 的上表面上，其质心位于
(
x
k
,
y
k
,
k
+
0.5
)
(x_k, y_k, k + 0.5)
(xk​,yk​,k+0.5)。

一个 $n$ – 塔是 $n$ 个柱体的堆叠。若在建造过程中（自底向上逐个添加柱体），每一步对应的子塔都是稳定的，则该塔是可行的。稳定性定义为：对于任意柱体 $s$，所有堆叠在它上方的柱体（包括它自身）组成的子系统的合质心，必须严格位于柱体 $s-1$ 的上表面圆盘内部（边界视为不稳定）。地面可视为半径无穷大的支撑面。

给定 $N$ 个柱体的设计参数，判断该塔是否可行。若不可行，输出导致倒塌的柱体编号 $k$（满足 $0<k<N$），即添加柱体 $k$ 后首次出现不稳定。

输入格式

• 每个测试用例以整数 $N$（$0<N<1000$）开始。
• 接下来 $N$ 行，每行三个整数
  x
  k
  ,
  y
  k
  ,
  r
  k
  x_k, y_k, r_k
  xk​,yk​,rk​，表示柱体 $k$ 的质心水平坐标和半径。
• 输入以 $N=0$ 结束。

输出格式

• 若所有 $N$ 个柱体添加后仍稳定，输出 Feasible。
• 否则，输出 Unfeasible k，其中 $k$ 是第一个导致不稳定的柱体编号。

题目分析

物理模型

每个柱体的体积
V
k
=
π
r
k
2
⋅
1
V_k = pi r_k^2 cdot 1
Vk​=πrk2​⋅1，由于材料均匀，质量
m
k
∝
r
k
2
m_k propto r_k^2
mk​∝rk2​。因此，在计算质心时，我们可以将每个柱体抽象为一个质点，位于其几何中心
(
x
k
,
y
k
,
k
+
0.5
)
(x_k, y_k, k + 0.5)
(xk​,yk​,k+0.5)，权重为
w
k
=
r
k
2
w_k = r_k^2
wk​=rk2​。

对于从柱体 $s$ 到柱体 $t$（$s\le t$）的子塔，其合质心的水平坐标为：

X
s
,
t
=
∑
i
=
s
t
w
i
⋅
x
i
∑
i
=
s
t
w
i
,
Y
s
,
t
=
∑
i
=
s
t
w
i
⋅
y
i
∑
i
=
s
t
w
i
X_{s,t} = frac{sum_{i=s}^t w_i cdot x_i}{sum_{i=s}^t w_i}, quad Y_{s,t} = frac{sum_{i=s}^t w_i cdot y_i}{sum_{i=s}^t w_i}
Xs,t​=∑i=st​wi​∑i=st​wi​⋅xi​​,Ys,t​=∑i=st​wi​∑i=st​wi​⋅yi​​

该子塔放置在柱体 $s-1$ 的上表面上，支撑面的圆心为
(
x
s
−
1
,
y
s
−
1
)
(x_{s-1}, y_{s-1})
(xs−1​,ys−1​)，半径为
r
s
−
1
r_{s-1}
rs−1​。稳定性条件为：

(
X
s
,
t
−
x
s
−
1
)
2
+
(
Y
s
,
t
−
y
s
−
1
)
2
<
r
s
−
1
2
left( X_{s,t} – x_{s-1} right)^2 + left( Y_{s,t} – y_{s-1} right)^2 < r_{s-1}^2
(Xs,t​−xs−1​)2+(Ys,t​−ys−1​)2<rs−12​

判断流程

建造过程自底向上进行。设当前已添加了柱体 $0,1,\dots ,t$（$t\ge 0$），则对于所有可能的支撑层 $s=1,2,\dots ,t$，需要检查子塔 $s\dots t$ 是否稳定地放置在柱体 $s-1$ 上。注意：

• 当 $t=0$ 时，只有柱体 $0$ 放在地面上，地面视为无穷大半径，故永远稳定。
• 当 $t\ge 1$ 时，必须检查所有 $s$。

一旦发现某个 $s$ 不满足条件，则塔在添加柱体 $t$ 后倒塌，输出 $t$ 即可。

复杂度分析

朴素做法：每添加一个柱体 $t$，对 $s$ 从 $1$ 到 $t$ 检查一次稳定性，每次检查需要计算
X
s
,
t
X_{s,t}
Xs,t​ 和
Y
s
,
t
Y_{s,t}
Ys,t​。若直接求和，时间复杂度为
O
(
N
3
)
O(N^3)
O(N3)，不可接受。

优化：预处理前缀和。

令：

W
i
=
∑
p
=
i
−
1
w
p
,
X
i
=
∑
p
=
i
−
1
w
p
⋅
x
p
,
Y
i
=
∑
p
=
i
−
1
w
p
⋅
y
p
W_i = sum_{p=0}^{i-1} w_p,quad X_i = sum_{p=0}^{i-1} w_p cdot x_p,quad Y_i = sum_{p=0}^{i-1} w_p cdot y_p
Wi​=p=0∑i−1​wp​,Xi​=p=0∑i−1​wp​⋅xp​,Yi​=p=0∑i−1​wp​⋅yp​

则：

∑
p
=
s
t
w
p
=
W
t
+
1
−
W
s
,
∑
p
=
s
t
w
p
x
p
=
X
t
+
1
−
X
s
,
∑
p
=
s
t
w
p
y
p
=
Y
t
+
1
−
Y
s
sum_{p=s}^{t} w_p = W_{t+1} – W_s,quad sum_{p=s}^{t} w_p x_p = X_{t+1} – X_s,quad sum_{p=s}^{t} w_p y_p = Y_{t+1} – Y_s
p=s∑t​wp​=Wt+1​−Ws​,p=s∑t​wp​xp​=Xt+1​−Xs​,p=s∑t​wp​yp​=Yt+1​−Ys​

这样每次检查可在 $O(1)$ 时间内计算出子系统的总重量和加权坐标和。总时间复杂度为
O
(
N
2
)
O(N^2)
O(N2)，对于 $N\le 1000$ 完全可行。

精度处理

直接使用整数运算比较
(
Δ
X
)
2
+
(
Δ
Y
)
2
(Delta X)^2 + (Delta Y)^2
(ΔX)2+(ΔY)2 与
r
2
⋅
(
∑
w
)
2
r^2 cdot (sum w)^2
r2⋅(∑w)2 可能产生溢出：

• 
  w
  i
  =
  r
  i
  2
  ≤
  10
  10
  w_i = r_i^2 le 10^{10}
  wi​=ri2​≤1010
• 累计
  W
  t
  +
  1
  ≤
  1000
  ×
  10
  10
  =
  10
  13
  W_{t+1} le 1000 times 10^{10} = 10^{13}
  Wt+1​≤1000×1010=1013
• 
  W
  2
  ≤
  10
  26
  W^2 le 10^{26}
  W2≤1026 远超 long long 范围（约
  9
  ×
  10
  18
  9 times 10^{18}
  9×1018）

因此，必须使用高精度或浮点数比较。由于题目允许浮点误差且 $N$ 不大，使用 long double 计算质心坐标并直接比较距离平方与
r
2
r^2
r2 是安全的，边界判断时加上微小容差。

解题步骤

1. 循环读入 $N$，若 $N=0$ 则结束。
2. 存储所有柱体的
   (
   x
   k
   ,
   y
   k
   ,
   r
   k
   )
   (x_k, y_k, r_k)
   (xk​,yk​,rk​)。
3. 初始化前缀和数组 $W$，$X$，$Y$，长度为 $N+1$，全部置 $0$。
4. 对于 $t=0$ 到 $N-1$：
   • 计算
     w
     t
     =
     r
     t
     2
     w_t = r_t^2
     wt​=rt2​。
   • 更新前缀和：
     W
     [
     t
     +
     1
     ]
     =
     W
     [
     t
     ]
     +
     w
     t
     W[t+1] = W[t] + w_t
     W[t+1]=W[t]+wt​，
     X
     [
     t
     +
     1
     ]
     =
     X
     [
     t
     ]
     +
     w
     t
     ⋅
     x
     t
     X[t+1] = X[t] + w_t cdot x_t
     X[t+1]=X[t]+wt​⋅xt​，
     Y
     [
     t
     +
     1
     ]
     =
     Y
     [
     t
     ]
     +
     w
     t
     ⋅
     y
     t
     Y[t+1] = Y[t] + w_t cdot y_t
     Y[t+1]=Y[t]+wt​⋅yt​。
   • 若 $t=0$，直接继续下一轮（地面稳定）。
   • 否则，对于 $s=1$ 到 $t$：
     • 子系统和：$subW=W[t+1]-W[s]$，$subX=X[t+1]-X[s]$，$subY=Y[t+1]-Y[s]$。
     • 计算子系统质心：$cx=subX/subW$，$cy=subY/subW$。
     • 计算质心到支撑面圆心的距离平方：
       d
       i
       s
       t
       2
       =
       (
       c
       x
       −
       x
       s
       −
       1
       )
       2
       +
       (
       c
       y
       −
       y
       s
       −
       1
       )
       2
       dist2 = (cx – x_{s-1})^2 + (cy – y_{s-1})^2
       dist2=(cx−xs−1​)2+(cy−ys−1​)2。
     • 若
       d
       i
       s
       t
       2
       ≥
       r
       s
       −
       1
       2
       −
       ϵ
       dist2 ge r_{s-1}^2 – epsilon
       dist2≥rs−12​−ϵ，则不稳定，记录 $collapseIdx=t$ 并跳出循环。
   • 若发现不稳定，跳出外层循环。
5. 根据 $feasible$ 标志输出结果。

代码实现

// Babel Towers
// UVa ID: 11116
// Verdict: Accepted
// Submission Date: 2026-04-26
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
struct Block {
    long long x, y, r;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N, N) {
        vector<Block> blocks(N);
        for (int i = 0; i < N; ++i)
            cin >> blocks[i].x >> blocks[i].y >> blocks[i].r;
        vector<long long> cumW(N + 1, 0);
        vector<long long> cumX(N + 1, 0);
        vector<long long> cumY(N + 1, 0);
        bool feasible = true;
        int collapseIdx = -1;
        for (int t = 0; t < N; ++t) {
            long long w = (long long)blocks[t].r * blocks[t].r;
            cumW[t + 1] = cumW[t] + w;
            cumX[t + 1] = cumX[t] + w * blocks[t].x;
            cumY[t + 1] = cumY[t] + w * blocks[t].y;
            for (int s = 1; s <= t; ++s) {
                long long subW = cumW[t + 1] - cumW[s];
                long long subX = cumX[t + 1] - cumX[s];
                long long subY = cumY[t + 1] - cumY[s];
                // 使用 long double 避免溢出
                long double cx = (long double)subX / subW;
                long double cy = (long double)subY / subW;
                long double dx = cx - blocks[s - 1].x;
                long double dy = cy - blocks[s - 1].y;
                long double dist2 = dx * dx + dy * dy;
                // 边界视为不稳定，加上微小容差
                if (dist2 >= (long double)blocks[s - 1].r * blocks[s - 1].r - 1e-12) {
                    feasible = false;
                    collapseIdx = t;
                    break;
                }
            }
            if (!feasible) break;
        }
        if (feasible) cout << "Feasiblen";
        else cout << "Unfeasible " << collapseIdx << "n";
    }
    return 0;
}

总结

本题的核心在于正确理解堆叠圆盘的稳定性物理模型，并将其转化为质心与支撑圆盘的几何约束。通过前缀和优化将
O
(
N
3
)
O(N^3)
O(N3) 的朴素算法降为
O
(
N
2
)
O(N^2)
O(N2)，同时利用 long double 处理数值溢出问题。注意边界条件（圆盘边缘视为不稳定）以及浮点比较时的容差处理，即可通过在线评测。