首页 > ACM题库 > HDU-杭电 > HDU 4234-Moving Points [解题报告]HOJ
2015
05-23

HDU 4234-Moving Points [解题报告]HOJ

Moving Points

问题描述 :

Consider a number of Target points in a plane. Each Target point moves in a straight line at a constant speed, and do not change direction. Now, consider a Chaser point that starts at the origin, and moves at a speed faster than any of the Target points. The Chaser point moves at a constant speed, but it is capable of changing direction at will. It will ‘Catch’ a Target point, and then move from there to catch another Target point, and so on.
Given the parameters of the Chaser point and the Target points, what is the least amount of time it takes the Chaser point to catch all of the Target points? ‘Catch’ simply means that the Catcher and the Target occupy the same point in the plane at the same time. This can be instantaneous; there’s no need for the Catcher to stay with the Target for any non-zero length of time.

输入:

There will be several test cases in the input. Each test case will begin with two integers
N C
Where N (1 ≤ N ≤ 15) is the number of Target points, and C (0 < C ≤ 1,000) is the speed of the Chaser point. Each of the next N lines will have four integers, describing a Target point:
X Y D S
Where (X,Y) is the location in the plane (-1000 ≤ X,Y ≤ 1,000) of that Target point at time 0, D (0 ≤ D < 360) is the direction of movement in Degrees (0 degrees is the positive X axis, 90 degrees is the positive Y axis), and S (0 ≤ S < C) is the speed of that Target point. It is assumed that all Target points start moving immediately at time 0.
The input will end with a line with two 0s.

输出:

There will be several test cases in the input. Each test case will begin with two integers
N C
Where N (1 ≤ N ≤ 15) is the number of Target points, and C (0 < C ≤ 1,000) is the speed of the Chaser point. Each of the next N lines will have four integers, describing a Target point:
X Y D S
Where (X,Y) is the location in the plane (-1000 ≤ X,Y ≤ 1,000) of that Target point at time 0, D (0 ≤ D < 360) is the direction of movement in Degrees (0 degrees is the positive X axis, 90 degrees is the positive Y axis), and S (0 ≤ S < C) is the speed of that Target point. It is assumed that all Target points start moving immediately at time 0.
The input will end with a line with two 0s.

样例输入:

2 25
19 19 32 10
6 45 133 19
5 10
10 20 45 3
30 10 135 4
100 100 219 5
10 100 301 4
30 30 5 3
0 0

样例输出:

12.62
12.54

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

#define for if(0); else for
const double PI=acos(-1.0);

struct Point{
	double x,y,vx,vy,t;
	Point(){}
	Point(double x,double y){
		this->x=x;
		this->y=y;
	}
	Point(double x,double y,double d,double v){
		this->x=x;
		this->y=y;
		this->vx=v*cos(d*PI/180.0);
		this->vy=v*sin(d*PI/180.0);
		this->t=0;
	}
	Point go(double t) const{
		Point ret=*this;
		ret.x+=vx*t;
		ret.y+=vy*t;
		return ret;
	}
};

int n;
Point p[16];
double spd;
double dp[16][1<<15];
bool vis[16][1<<15];

double dis(const Point &a,const Point &b){
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}

double cost(const Point &a,const Point &b){
	Point ta=Point(b.x-a.x,b.y-a.y);
	Point v=Point(b.vx,b.vy);
	double V=dis(v,Point(0,0));
	double D=dis(ta,Point(0,0));
	double A=V*V-spd*spd;
	double C=D*D;
	double B=-2.0*(ta.x*v.x+ta.y*v.y);
	return (B-sqrt(B*B-4*A*C))/2.0/A;
}


int main() {
	setbuf(stdout,NULL);
	while(scanf("%d%lf",&n,&spd) &&(n!=0&&spd!=0)){
		p[0]=Point(0,0,0,0);
		for(int i=1;i<=n;i++){
			double x,y,d,v;
			scanf("%lf%lf%lf%lf",&x,&y,&d,&v);
			p[i]=Point(x,y,d,v);
		}
		memset(vis,0,sizeof(vis));
		vis[0][0]=1;
		for(int stat=1;stat<1<<n;stat++){
			for(int i=1;i<=n;i++){
				int prev=stat;
				prev &= ~ ( 1<< (i-1) );
				if(prev==stat) continue;
				for(int j=0;j<=n;j++) if(j!=i){
					if(vis[j][prev]){
						double val=dp[j][prev]+cost(p[j].go(dp[j][prev]),p[i].go(dp[j][prev]));
						if(!vis[i][stat]) vis[i][stat]=1,dp[i][stat]=val;
						else dp[i][stat]=min(dp[i][stat],val);
					}
				}
			}
		}
		double ans=dp[1][(1<<n)-1];
		for(int i=1;i<=n;i++) ans=min(ans,dp[i][(1<<n)-1]);
		printf("%.2lf\n",ans);
	}
	return 0;
}