UVa 10012 - How Big Is It?

链接

传送门

题意

给出$n$个圆,输出让它们共切线时最小的宽度。

思路

枚举全排列,注意再枚举的过程中注意随时维护右边界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 10;
const int per[maxn] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
double a[maxn], p[maxn];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%lf", &a[i]);
}
int cnt = per[n];
double ans = 1e9;
while (cnt--) {
p[0] = a[0];
double cur = 2 * a[0];
for (int i = 1; i < n; ++i) {
p[i] = a[i];
for (int j = 0; j < i; ++j) {
p[i] = max(p[i], p[j] + 2 * sqrt(a[i] * a[j]));
}
cur = max(cur, p[i] + a[i]);
}
ans = min(ans, cur);
next_permutation(a, a + n);
}
printf("%.3lf\n", ans);
}
return 0;
}

支付宝扫码领红包