首页 > ACM题库 > HDU-杭电 > HDU 4170-Supply Mission-枚举-[解题报告]HOJ
2015
05-23

HDU 4170-Supply Mission-枚举-[解题报告]HOJ

Supply Mission

问题描述 :

You are to fly a helicopter to bring supplies to a number of submarines that are currently moving across the ocean. You will be given the coordinates of the helicopter base and each submarine. Each submarine is travelling constantly at a heading and speed specified by the velocity vector (vx, vy), meaning that after 1 hour it would have travelled vx km in the x direction and vy km in the y direction (vx and vy may be negative). The length of the vector is the speed. The helicopter is capable of travelling at a constant speed in any direction (assume that acceleration and deceleration are instantaneous). The helicopter must land on each submarine at least once, and it takes 1 hour at each stop to unload the supplies and refuel. Each submarine rises to the surface at the appropriate landing time, and submerges once the helicopter leaves. You may assume that the velocity of each submarine is not affected by any change of its travelling depth. The helicopter can carry enough supplies for all submarines without having to return to the base. All coordinates have km as units, and all velocities and speeds have km/h as units.

Find the shortest time for the helicopter to bring supplies to each submarine from the base and return to its base.

输入:

The input consists of a number of cases. Each case starts with a line containing the integer N (1 <= N <= 8) specifying the number of submarines. The next N lines contain 4 integers separated by a space: the initial (x,y) coordinates of the i-th submarine and its velocity vector. The last line of each case contains 3 integers specifying the (x,y) coordinates of the helicopter base and the speed of the helicopter. The end of input is indicated by a case that starts with N = 0, and this last case should not be processed. All input integers have absolute value at most 1000. You may assume that the helicopter travels at a greater speed than every submarine. Note that the paths of the submarines may cross each other or even the helicopter base, but since they can adjust their depth there will be no collisions.

输出:

The input consists of a number of cases. Each case starts with a line containing the integer N (1 <= N <= 8) specifying the number of submarines. The next N lines contain 4 integers separated by a space: the initial (x,y) coordinates of the i-th submarine and its velocity vector. The last line of each case contains 3 integers specifying the (x,y) coordinates of the helicopter base and the speed of the helicopter. The end of input is indicated by a case that starts with N = 0, and this last case should not be processed. All input integers have absolute value at most 1000. You may assume that the helicopter travels at a greater speed than every submarine. Note that the paths of the submarines may cross each other or even the helicopter base, but since they can adjust their depth there will be no collisions.

样例输入:

5
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0
0 0 1
3
1 2 3 4
2 2 40 23
7 8 22 10
0 0 50
0

样例输出:

Case 1: 15 hour(s) 0 minute(s) 0 second(s)
Case 2: 5 hour(s) 59 minute(s) 50 second(s)

题意:飞机在任意位置sx,sy,速度为v,潜艇位置为pa[i].x,p[i].y,速度向量为p[i].vx,p[i].vy,问飞机和这些潜艇相遇并且要一个小时卸载货物,最后回到飞机起点,问至少需要多长时间

思路:n<=8,很小,直接全排列n个潜艇的位置,然后枚举经过所有潜艇所花费的最少时间

刚开始一直出错,初始化错了,注意要每次一个全排列要更新原来坐标的值

代码:

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define eps 1e-8
int n;
double sx,sy,v;
struct node
{
    double x,y;
   double vx,vy;
} a[10],pa[10];
int p[10];
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void solve(int g)
{
    double mmin=-1,ans,gx,gy;
    do
    {
        gx=sx;
        gy=sy;
        ans=0;
        for(int i=0;i<n;i++)
        a[i]=pa[i];
        for(int i=0; i<n; i++)
        {
            double A,B,aa,bb,cc,t;
            A=a[p[i]].x-gx;
            B=a[p[i]].y-gy;
            aa=a[p[i]].vx*a[p[i]].vx+a[p[i]].vy*a[p[i]].vy-v*v;
            bb=2*(A*a[p[i]].vx+B*a[p[i]].vy);
            cc=A*A+B*B;
            if(fabs(aa)<eps)t=-cc/bb;
            else
            {
                t=(-bb+sqrt(bb*bb-4*aa*cc))/(2*aa);
                if(t<0)
                    t=(-bb-sqrt(bb*bb-4*aa*cc))/(2*aa);
            }
            t+=1.0;
            for(int j=i; j<n; j++)
            {
                a[p[j]].x+=t*a[p[j]].vx;
                a[p[j]].y+=t*a[p[j]].vy;
            }
            gx=a[p[i]].x;
            gy=a[p[i]].y;
            ans+=t;
        }
        ans+=dis(sx,sy,gx,gy)/v;
        if(mmin<0 || ans<mmin)
        {
            mmin=ans;
        }
    }
    while(next_permutation(p,p+n));
    int h,m,s;
    s=(int)(mmin*3600+0.9999);
    m = s/60;
    s %= 60;
    h = m/60;
    m %= 60;
    printf("Case %d: %d hour(s) %d minute(s) %d second(s)\n",g,h,m,s);
}
int main()
{
    int g=0;
    while(scanf("%d",&n),n)
    {
        g++;
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf",&pa[i].x,&pa[i].y,&pa[i].vx,&pa[i].vy);
        }
        scanf("%lf%lf%lf",&sx,&sy,&v);
        for(int i=0;i<n;i++)
        p[i]=i;
        solve(g);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm18810549519/article/details/12259167