首页 / 软件开发 / 数据结构与算法 / UVa 10012 How Big Is It？ （枚举和细节）

UVa 10012 How Big Is It？ （枚举和细节）2014-07-07 synapse7 http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=953

思路：

最多8个球，直接枚举。

注意：

1.

由于一个圆不一定与圆心横坐标与其横坐标最接近的圆相切，所以判断一个圆圆心横坐标的实际位置要一一比较在它左边的每个圆，取最大值。

2. 由于圆心横坐标在最右边的圆不一定与箱子最右端接触（如上图，我们的算法是保证每个圆的实际圆心横坐标尽量小，即往左边靠），所以箱子长度=max{圆实际圆心横坐标+圆的半径}

完整代码：

01./*0.098s*/02.03.#include<bits/stdc++.h>04.using namespace std;05.06.double a[10], r[10];07.08.///计算圆心的实际横坐标09.inline void calc（int id）10.{11.double x;12.for （int i = 0; i < id; ++i）13.{14.x = sqrt（（a[i] + a[id]） * （a[i] + a[id]） - （a[i] - a[id]） * （a[i] - a[id]）） + r[i];15.r[id] = max（r[id], x）;16.}17.}18.19.int main（）20.{21.int T, n, i;22.double ans, tmp;23.scanf（"%d", &T）;24.while （T--）25.{26.scanf（"%d", &n）;27.for （i = 0; i < n; ++i） scanf（"%lf", &a[i]）;28.sort（a, a + n）;29.ans = 1e100;30.do31.{32.memcpy（r, a, sizeof（a））;33.for （i = 1; i < n; ++i） calc（i）;///计算圆心的实际横坐标34.tmp = 0.0;35.for （i = 0; i < n; ++i） tmp = max（tmp, r[i] + a[i]）;///这么算是因为不一定最右边那个就靠在箱子右侧36.ans = min（ans, tmp）;37.}38.while （next_permutation（a, a + n））;39.printf（"%.3f
", ans）;40.}41.return 0;42.}