hdu 4170 Supply Mission

KIDx的解题报告

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4170

 

题意：飞机在位置(x0,y0), 飞行速度为v km/h，

有N(0<N<8)艘潜艇分别为(px[i],py[i])速度向量为(vx[i],vy[i])km/h,坐标单位为km
飞机必须在每艘潜艇上要一小时卸载货物，最后飞回原来的位置(x0,y0)，求最少时间花费，用时分秒输出。

 

解析：

n很小，可以暴力枚举全排列进行模拟，重点是如何求出飞机与潜艇的最小相遇时间：（化简成一元二次方程求解即可）

 

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
#define M 10
#define eps 1e-8

struct point{
    double x, y;
};

double dis (point a, point b)
{
    return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int main()
{
    point ini, S, p[M], s[M];
    int n, cc = 0, i, j, k, vx[M], vy[M], v, id[M];
    double ans, tp;
    while (scanf ("%d", &n), n)
    {
        for (i = 0; i < n; i++)
            scanf ("%lf%lf%d%d", &s[i].x, &s[i].y, vx+i, vy+i);
        scanf ("%lf%lf%d", &ini.x, &ini.y, &v);
        for (i = 0; i < n; i++) id[i] = i;
		//暴力枚举全排列进行模拟
        ans = -1;
        do {
            for (i = 0; i < n; i++) p[i] = s[i];
            S = ini;
			//上面是一次模拟的初始化
            tp = 0;
            for (i = 0; i < n; i++)
            {
                k = id[i];
				//计算飞机从S飞到p[K]的最少时间
                double dt, a, b, c, A, B;
                A = p[k].x - S.x;
                B = p[k].y - S.y;
                a = vx[k]*vx[k] + vy[k]*vy[k] - v*v;
                b = 2 * (A*vx[k] + B*vy[k]);
                c = A*A + B*B;
                if (fabs (a) < eps) dt = -c/b;
                else
                {
                    dt = (-b + sqrt (b*b - 4*a*c)) / (2*a);
                    if (dt < 0) dt = (-b - sqrt (b*b - 4*a*c)) / (2*a);
                }

                dt += 1.0;					//一个小时卸货
                for (j = i; j < n; j++)	   //所有潜艇走了dt的时间，更新他们的坐标
                {
                    p[id[j]].x += dt * vx[id[j]];
                    p[id[j]].y += dt * vy[id[j]];
                }
                S = p[k];					//飞机现在在p[K]上准备飞往下一个地点
                tp += dt;
            }
            tp += dis (S, ini) / v;			//飞回基地
            if (ans < 0 || tp < ans) ans = tp;		//更新最小值
        } while (next_permutation (id, id+n));
        int h, m, s;
		//题目信息：The time should be rounded up to the next second.
        s = int (ans*3600 + 0.99999);
        m = s / 60; s %= 60;
        h = m / 60; m %= 60;
        printf ("Case %d: %d hour(s) %d minute(s) %d second(s)\n",
			++cc, h, m, s);
    }
    return 0;
}