Problem C
Yoyodyne Propulsion Systems
Input: Standard Input

Output: Standard Output

Three years ago, Yoyodyne Propulsion Systems, Inc., of the planet Tau Ceti Prime, received a generous contract from the Department of Stellar Defense (DoSD) to provide the StarBlazers Forces with their next-generation engines. These engines are primarily to be used for ferrying large cargos of supplies to several outposts in the outer rim.

These engines have special properties. First of all, they only have two speeds: zero and really-really-fast. Secondly, they do not require any time to go from one speed to the other; They can instantly go from zero to really-really-fast, and vice-versa.

In order to receive continued funding, Yoyodyne must provide the DoSD with a demonstration that they have made significant progress towards developing these engines (It's always the same old story with government funding, isn't it?!?!). To do this, the DoSD has set up a series of buoys in a remote part of the galaxy, and tasked Yoyodyne with navigating each sequence of buoys given a certain amount of fuel at the start of each sequence. The engines would keep traveling until the last bouy is reached or it runs out of fuel, whichever occurs first. We would assume that the fuel consumtion is uniform throughout the travel.

Assume that each mission starts at location (0,0,1). At the start of each mission, and as each buoy is reached, the next buoy to visit is determined by the closest buoy in the mission that has not yet been visited. In case of a tie, the buoy information that comes first in the input is given preference. Your job is to write a program to check if the current prototype engines can successfully complete each mission, given certain mission parameters, and provide some statistics about engine performance.

Input

The input to this problem consists of maximum 10 missions.

The first line of each mission consists four of integers. The first integer, f (1 <= f <= 20,000), is the amount of fuel (in kernels) in the tanks at the start of the mission, the next number, b (1 <= b <= 100) is the burn-rate of the fuel in kernels per second, the third number, r (1 <= r <= 200) defines how fast really-really-fast is for this mission, in lightyears per second and the fourth integer n(1<=n<=20) denotes the number of buoys in the mission. Each of the next n lines contains three integers x,y,z (-2000<=x,y,z<=2000) defining the (x,y,z) coordinates, in lightyears, of one buoys in this mission. The coordinates can range from -2000 to 2000 inclusive. If two buoys have the same coordinate they should be considered as two different buoys, although the distance between them is zero.

The end of input is signified by a line where f=b=r=n=0..

Output

You are to output one line for each mission. The output line begins with the word "Mission"  followed by a space, the mission number, a colon, and a space. If the mission can be completed, you are to output the word "SUCCESS!!", followed by a space, the word "Time:", a space, the total amount of time to complete the mission, in seconds, followed by two spaces, the word "Traveled:", a space, the total distance traveled for this mission, in lightyears, followed by two spaces, the words "Fuel Left:", a space, and the amount of fuel left in the tanks, in kernels.

If the mission cannot be completed, you are to output the word "FAILURE!!", followed by a space, the word "Traveled:", a space, the total distance traveled for this mission, in lightyears, followed by two spaces, the words "From Home:", a space, the distance from the current location to the final buoy, in lightyears, assuming you would traverse all remaining legs of the mission. All numbers in the output (Except the serial of mission) should be rounded to two digits after the decimal point.

Sample Input    Output for Sample Input

3 1 1 2

0 0 2 

0 0 3

1 1 1 2  

0 0 2 

0 0 3 

200 1 200 4 

2000 0 0 

-2000 0 0 

-2000 0 0        

-2000 -2000 -2000 

0 0 0 0

Problem setter: Robert W. Lindeman

Special Thanks: Shahriar Manzoor, Monirul Hasan

題目描述：

給定起點 (0, 0, 1)，每次找一個鄰近且還沒走訪過的點前進，會給燃料總量、每秒消耗多少燃料，以及可以跑多快。首先考慮可以走完所有點，會得到一條路徑。

如果燃料不足，可能會停留在點與點的中間，計算停止點到路徑最後一點的距離。

反之，輸出剩餘的燃料。

如果存在鄰近不止有一個，則選擇輸入順序最前面的。

#include <stdio.h>
#include <math.h>

int main() {
    double f, b, r;
    double x[105], y[105], z[105];
    int n, cases = 0;
    int i, j, k;
    //freopen("out.txt","w+t",stdout);
    while(scanf("%lf %lf %lf %d", &f, &b, &r, &n) == 4 && n) {
        for(i = 0; i < n; i++)
            scanf("%lf %lf %lf", &x[i], &y[i], &z[i]);
        int used[105] = {};
        double px = 0, py = 0, pz = 1;
        double tx, ty, tz;
        double travel = 0, time = 0;
        double home;
        int fail = 0;
        for(i = 0; i < n; i++) {
            double mn = 1e+30;
            int idx = 0;
            for(j = 0; j < n; j++) {
                if(used[j]) continue;
                double dist = sqrt(pow(px-x[j], 2)+pow(py-y[j], 2)+pow(pz-z[j], 2));
                if(dist+1e-8 < mn) {
                    mn = dist;
                    idx = j;
                }
            }
            used[idx] = 1;
            if(f < mn/r*b && fail == 0) {
                fail = 1;
                home = travel + f/b*r;
                tx = px + (f/b*r/mn)*(x[idx]-px);
                ty = py + (f/b*r/mn)*(y[idx]-py);
                tz = pz + (f/b*r/mn)*(z[idx]-pz);
            }
            travel += mn;
            time += mn/r;
            f -= mn/r*b;
            px = x[idx], py = y[idx], pz = z[idx];
        }
        printf("Mission %d: ", ++cases);
        if(fail) {
            printf("FAILURE!! Traveled: %.2lf  From Home: %.2lf\n", home, sqrt(pow(tx-px,2)+pow(ty-py,2)+pow(tz-pz,2)));
        } else {
            printf("SUCCESS!! Time: %.2lf  Traveled: %.2lf  Fuel Left: %.2lf\n", time, travel, f);
        }
    }
    return 0;
}