首页 > ACM题库 > HDU-杭电 > HDU 2906-Robintron[解题报告]HOJ
2014
02-21

HDU 2906-Robintron[解题报告]HOJ

Robintron

问题描述 :

It is during the great war in the year 2240 that the Robinson family decides to leave the human empire, in search for more peaceful and quiet places. The Robinsons already have a planet in mind to which they wish to travel and want to get there as soon as possible. However, because all vehicles capable of spaceight are being used for the war, the Robinson family has no way to escape to other planets by means of ordinary space ight. It is therefore that Joe Robinson, the father of the family, created the Robintron. The Robintron is a vehicle that is capable of travelling from one planet’s surface to another by only using the forces of gravity.
It is the gravitational pull of a planet that keeps the Robintron on a planet’s surface. This pull extends as far as the planet’s gravity well, a circular area around the center of the planet, which is generated by the planet’s mass. However, these gravity wells can also be used to assist the Robintron in leaving a planet by the way of planet hopping. Planet hopping can be performed when the Robintron is on the surface of a planet and comes within the area of another planet’s gravity well. The Robintron uses the other planet’s gravity well to gain enough momentum to escape into space, and to land on the other planet’s surface. Leaving a planet and subsequently landing on another one takes no signicant amount of time.

Planet hopping has some disadvantages. The Robintron must be within the gravity well of a planet other than the one it resides on, to be able to effectively use it for planet hopping. However, as the planets rotate around a star (which they all do in perfectly circular orbits), their position continuously changes according to their rotational speed. Thus, it can take up some time for the Robintron to enter the gravity well of a particular planet. Also, as soon as the Robintron chooses to enter the gravity well of a planet, it will move along with that planet around the star. Therefore, this could mean that another planet’s gravity well may never come in reach of the Robintron.

Given a list of planets in a star system, a starting position and destination, write a program that determines how many days it will take (using the ceiling function, i.e. ceiling(2.3) = 3) for the Robintron to travel to its destination, given that it travels via the fastest route possible.

Because in most star systems all planets are positioned around the star in a disc, only two dimensions have to be taken into account. Also, a planet is assumed to be a single point in space, and the Robintron’s coordinates are equal to those of the planet it resides on.

输入:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line containing the positive integer number m (0 < m < 1000), the number of planets in the star system (excluding the star which always resides at position [0, 0]);
Per planet a line containing 4 numbers x (-1e10 <= x <=1e10) and y (-1e10 <=y <=1e10), the x-coordinate and y-coordinate of the planet relative to the star at the start of the Robintron’s journey respectively; r (0 < r = 1e5) the radius of the planet’s gravity well and s (0 < =s <=2∏(this symbol is 3.1415926….)) the speed, in radians per day, at which the planet rotates (counterclockwise) around the central star. The numbers are separated by a space. The Robintron’s journey always starts at the first listed planet and its destination is always the last listed planet, which is always reachable from the Robintron’s starting position. The star (at position [0, 0]) is too hot for the Robintron and cannot be used for planet hopping.

输出:

The first line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line containing the positive integer number m (0 < m < 1000), the number of planets in the star system (excluding the star which always resides at position [0, 0]);
Per planet a line containing 4 numbers x (-1e10 <= x <=1e10) and y (-1e10 <=y <=1e10), the x-coordinate and y-coordinate of the planet relative to the star at the start of the Robintron’s journey respectively; r (0 < r = 1e5) the radius of the planet’s gravity well and s (0 < =s <=2∏(this symbol is 3.1415926….)) the speed, in radians per day, at which the planet rotates (counterclockwise) around the central star. The numbers are separated by a space. The Robintron’s journey always starts at the first listed planet and its destination is always the last listed planet, which is always reachable from the Robintron’s starting position. The star (at position [0, 0]) is too hot for the Robintron and cannot be used for planet hopping.

样例输入:

2
3
10.0 0.0 1.0 1.570796325
-13.0 0.0 3.1 3.14159265
17.0 0.0 4.1 0.0
5
10.0 0.0 1.1 1.0
12.0 0.0 1.1 2.0
13.0 0.0 1.1 1.0
0.0 11.0 1.1 3.14159265
14.0 0.0 1.1 1.0

样例输出:

3
7

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;
typedef double db;
const db PI = acos(-1.0);
const db eps = 1e-15;
const db oo = 1e100;
struct pt{
 db x,y;
 pt(){}pt(db x,db y):x(x),y(y){}
 pt operator -(pt a){return pt(x-a.x,y-a.y);}
 db operator *(pt a){return x*a.x+y*a.y;}
 db operator &(pt a){return x*a.y-y*a.x;}
 db len(){return sqrt(x*x+y*y);}
 db ang(){return atan2(y,x);}
 void getP(){scanf("%lf%lf",&x,&y);}
};
struct circle{
 pt o;
 db r,a,l;
 void getC(){o.getP();l = o.len();a = o.ang();scanf("%lf",&r);}
};
struct box{
 db s,d,c;
};
const int MaxC = 1024;
circle cl[MaxC];
box fm[MaxC][MaxC];
db dis[MaxC],w[MaxC];
bool U[MaxC];
int sign(db x){return (x > eps)-(x < -eps);}
db calTime(int x,int y,db ct){
 box &cb = fm[x][y];
 if (cb.c > oo / 2)
 return oo;
 if (sign(cb.c) == 0)
 return ct;
 db ft = cb.s+floor((ct-cb.s) / cb.c-1.0)*cb.c;
 while (sign(ft-ct) < 0 && sign(ct-ft-cb.d) > 0)
 ft += cb.c;
 return max(ft,ct);
}
int main(){
 int tCase;
 scanf("%d",&tCase);
 for (int ct = 1;ct <= tCase;ct++){
 int N;
 scanf("%d",&N);
 for (int i = 0;i < N;i++){
 cl[i].getC();
 scanf("%lf",&w[i]);
 }
 for (int i = 0;i < N;i++)
 for (int j = 0;j < N;j++)if (i != j){
 box &cb = fm[i][j];
 db a = cl[i].l,b = cl[j].l,c = cl[j].r;
 if (sign(c-fabs(a-b)) < 0){
 cb.c = oo;
 continue;
 }
 if (sign(c-a-b) >= 0){
 cb.c = 0.0;
 continue;
 }
 db cd = (a*a+b*b-c*c) / (2.0*a*b);
 if (sign(cd-1.0) >= 0) cd = 1.0;
 if (sign(cd+1.0) <= 0) cd = -1.0;
 db da = acos(cd);
 db cw = w[i]-w[j];
 db ca = cl[j].a-cl[i].a;
 while (sign(ca+PI) < 0) ca += PI*2;
 if (sign(cw) == 0){
 if (sign(fabs(ca)-da) <= 0)
 cb.c = 0.0;
 else
 cb.c = oo;
 continue;
 }
 cb.c = PI*2.0 / fabs(cw);
 cb.d = da*2.0 / fabs(cw);
 cb.s = ca / cw-cb.d*0.5;
 //printf("%d %d : %.12f %.12f %.12f | %.12f %.12f %.12f\n",i,j,cb.s,cb.d,cb.c,da,cd,(a*a+b*b-c*c) / (2.0*a*b));
 }
 memset(U,0,sizeof(U[0])*N);
 dis[0] = 0.0;
 for (int j = 1;j < N;j++)
 dis[j] = calTime(0,j,0.0);
 U[0] = true;
 for (int i = 1;i < N;i++){
 int mj = -1;
 db md = oo;
 for (int j = 0;j < N;j++)
 if (!U[j] && dis[j] < md)
 md = dis[mj = j];
 //printf("%d : %.12f\n",mj,md);
 if (mj == N-1) break;
 if (mj == -1){
 puts("Error");
 while (1);
 }
 U[mj] = true;
 for (int j = 0;j < N;j++)
 if (!U[j]){
 db nd = calTime(mj,j,md);
 dis[j] = min(nd,dis[j]);
 }
 }
 if (dis[N-1] > oo / 2) while(1);
 printf("%.f\n",ceil(dis[N-1]));
 }
 return 0;
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢