解題區/解題區 - UVa

UVa 915 - Stack of Cylinders

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

根據順序依據擺放半徑為 r 的圓，求最後的總長，以及從端點開始碰壁到另外一端所有圓編號，保證不會有三個圓相互接觸。

Sample Input

1
2
3
4
5
6
7
8
7
3
25
35
5
4
32
4

Sample Output

1
2
3
4
5
183.1
3
2
3
6

Solution

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
39
40
41
42
43
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, cases = 0;
    while(scanf("%d", &n) == 1) {
        if(cases++)	puts("");
        double radius[128], posX[128];
        for(int i = 1; i <= n; i++)
            scanf("%lf", &radius[i]);
            
        double mx = 0;
        int prev[128] = {}, tail = 0;
        for(int i = 1; i <= n; i++) {
            double x = radius[i];
            for(int j = 1; j < i; j++) {
                double nx = sqrt(pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2)) + posX[j];
                if(nx > x) 
                    prev[i] = j;
                x = max(x, nx);
//				printf("sqrt = %lf\n", pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2));
            }
//			printf("prev[%d] %d\n", i, prev[i]);
            posX[i] = x;
            if(posX[i] + radius[i] > mx)
                tail = i;
            mx = max(mx, posX[i] + radius[i]);
        }
        printf("%.1lf\n", mx);
        vector<int> ret;
        while(tail) {
            ret.push_back(tail);
            tail = prev[tail];
        }
        printf("%d\n", ret.size());
        for(int i = ret.size() - 1; i >= 0; i--)
            printf("%d\n", ret[i]);
    }
    return 0;
}