UVa 10012 - How Big Is It? | Sengxian's Blog

UVa 10012 - How Big Is It?

Published on 2016-01-20

描述

给出 $n(n\le8)$ 个圆的半径，你必须将他们贴着底部排放在一个长方形里面，问如何摆放能使长方形的宽度最短？输出这个宽度。

样例输入

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

样例输出

9.657
16.000
12.657

分析

文章底部有数据
此题看似就是普通的暴力，枚举排列的题，然而却有一堆坑点：

可能出现放了一个大圆，大圆底下放了一个很小的圆，这时右边界应该是大圆的边界而不是小圆的。这种情况统计最右边的边界即可。
可能一开始在左下角放了一个小圆，接着放了一个大圆，这时左边界是大圆的边界而不是小圆的边界。这种情况统计一下最大的超出部分即可。
可能出现放了一个大圆，大圆底下放了一个很小的圆，再放一个圆会跟大圆相交，这种情况就要判断冲突，不断的计算跟前面一个圆相切，跟前前个圆相切，直到找到不存在冲突的摆放。
可能答案会很大，所以答案初始化为 DBL_MAX（在 cfloat 里面）

代码

//  Created by Sengxian on 1/20/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10012 暴力 + 思维
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cfloat>
using namespace std;

inline int ReadInt() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    do {
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(isdigit(ch));
    return x;
}

const int maxn = 8 + 1;
double r[maxn], center[maxn];
int n;

int dcmp(double a, double b) {
    if(fabs(a - b) < 1e-8) return -1;
    return a < b;
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt();
        for(int i = 0; i < n; ++i)
            scanf("%lf", r + i);
        sort(r, r + n);
        double ans = DBL_MAX;
        do {
            double Max = r[0] * 2, add = 0;
            center[0] = r[0];
            for(int i = 1; i < n; ++i) {
                for(int j = i - 1; j >= 0; --j) {
                    center[i] = center[j] + 2 * sqrt(r[i] * r[j]);
                    bool flag = true;
                    for(int k = 0; k < j; ++k) 
                        if(dcmp(hypot(r[i] - r[k], center[i] - center[k]), r[i] + r[k]) == 1) {flag = false; break;}
                    if(flag) break;
                }
                if(dcmp(center[i] - r[i], 0) == 1) add = max(add, fabs(center[i] - r[i]));
                Max = max(Max, center[i] + r[i]);
            }
            ans = min(ans, Max + add);
        }while(next_permutation(r, r + n));
        printf("%.3lf\n", ans);
    }
    return 0;
}

附加输入

100
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
3 0.196 0.009 0.735
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
3 0.467 0.889 0.461
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
6 1.419 5.220 1.208 0.714 1.741 8.151
7 0.453 2.879 1.834 3.639 1.361 0.558 1.280
8 10.519 0.553 4.513 0.911 1.170 0.293 0.678 1.463
2 1.069 0.616
5 1.780 3.458 2.220 0.659 0.750
8 0.146 1.085 7.379 0.992 4.334 3.427 0.608 2.375
1 0.155
5 0.119 2.052 0.379 2.150 0.693
4 63.499 0.249 3.666 0.322
5 1.890 4.796 0.583 0.187 0.347
1 1.079
4 0.209 1.862 1.430 5.867
8 3.265 0.590 0.054 1.583 0.074 1.585 0.525 0.989
4 2.232 7.205 150.375 1.467
1 11.740
6 10.779 3.807 1.716 0.428 0.536 1.224
4 1.071 2.685 0.794 0.117
4 0.608 0.486 0.135 4.533
1 0.469
8 2.294 0.756 10.556 3.538 2.250 0.383 0.858 1.160
3 2.463 1.446 1.809
5 2.174 0.154 0.322 0.539 0.847
7 0.429 1.694 2.170 0.214 0.369 0.275 8.182
5 2.159 0.739 1.132 0.733 0.328
3 7.906 3.212 1.724
1 3.759
4 2.750 1.045 1.434 19.391
2 0.241 12.710
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411
3 2.301 1.375 0.298
2 0.376 0.532
4 2.275 0.261 0.087 2.705
5 0.605 1.057 0.257 0.706 0.861
3 0.203 0.627 0.848
1 4.048
5 3.357 0.641 4.038 0.864 0.667
8 0.252 0.416 1.932 0.365 0.621 0.502 8.299 0.318
2 40.436 3.087
7 0.682 2.496 0.322 0.786 0.128 0.625 0.438
4 1.042 2.291 0.724 1.504
8 1.460 5.581 0.001 25.125 1.713 2.704 0.342 0.716
6 0.102 0.469 0.859 4.451 2.170 1.602
8 1.830 14.377 0.517 0.685 1.184 0.001 1.011 1.385
6 0.855 0.000 1.823 0.768 0.426 1.157
5 0.647 2.051 0.537 1.676 0.339
3 3.623 0.364 0.994
8 0.947 1.024 0.263 0.773 1.279 4.074 49.961 0.065
2 6.345 16.925
5 4.651 0.156 1.075 0.480 2.629
5 1.256 0.227 0.054 0.035 1.912
2 1.203 0.751
7 5.175 0.518 1.108 8.091 0.274 1.003 0.555
6 0.291 0.175 0.370 7.216 0.554 1.628
7 0.847 0.676 0.577 0.492 1.407 0.868 10.257
2 0.812 1.108
6 1.286 19.802 0.499 0.333 0.598 13.306
3 0.688 0.263 21.964
1 0.748
8 0.203 1.499 23.346 1.314 2.114 0.833 1.757 14.082
7 7.280 0.942 0.389 1.521 1.467 0.963 2.634
6 0.588 0.239 0.647 2.450 1.536 0.291
8 22.087 1.160 10.010 0.527 1.168 0.720 0.184 0.670
7 3.225 1.402 1.486 2.549 1.023 1.008 2.263
2 0.955 1.202
5 3.073 7.774 6.587 8.906 1.282
6 0.301 0.835 4.213 0.848 5.414 1.315
4 0.731 2.590 2.308 0.235
1 1.250
8 0.383 3.919 0.738 0.429 0.663 0.698 1.331 1.531
7 1.280 0.356 0.686 1.039 0.680 0.058 0.490
6 1.031 0.174 1.945 0.773 0.680 0.466
8 0.413 0.689 4.510 0.694 1.453 3.161 0.971 0.283
3 0.781 1.030 1.666
3 0.061 1.953 1.654
3 0.036 0.741 0.477
3 1.826 2.268 2.851
7 0.319 2.537 1.363 35.278 0.172 6.054 4.533
2 5.517 1.447
2 0.226 0.493
8 2.559 0.443 4.470 1.445 1.162 0.258 0.193 1.644
4 0.563 3.274 1.186 0.803
8 0.303 7.870 17.105 0.734 1.000 6.424 3.592 2.105
7 1.028 2.475 1.486 0.505 0.480 0.133 1.702
2 0.528 1.190
4 8.753 0.326 0.944 0.843
2 0.870 1.001
4 0.324 0.899 0.772 5.190
8 0.182 2.026 12.486 2.303 1.066 4.099 0.923 1.286
7 2.644 0.931 0.367 0.779 0.618 0.190 11.166
8 1.903 0.002 1.174 3.766 0.789 1.874 7.221 0.830
8 0.579 0.657 0.518 0.567 19.806 0.080 0.186 2.428
6 0.778 3.006 5.973 8.024 0.042 0.268
7 0.148 0.226 3.190 0.146 1.708 0.398 0.317
5 2.595 0.559 0.306 1.292 1.908

附加输出

UVa 1533 - Moving Pegs UVa 1508 - Equipment