Algoogle

Algorithm for Programming Contest

AOJ 2586 Wish upon a shooting star

Category: AOJ Tag: math

Wish upon a shooting star

問題概要


3次元空間上のn個の流れ星の初期位置, 速さと向き, 半径, 半径の現象速度が与えられる.
これらは半径が0になるか, 互いにぶつかると消滅する.
それぞれの流れ星の消滅するまでの時間を求めよ.

解法


幾何要素は皆無.
2つの星の衝突する時間をtとしてt秒後の位置の距離が半径を足しあわせたものになるので2次方程式を立てる.
これを解けば衝突するかどうか(判別式), またその時間を求める事ができる.
方程式は定数項をまとめていくように解くと間違いが少なくなる.
あとは解から正の時間かつどちらの星も自然消滅していない時間ならその時間を返せば良い.

この衝突時間と自然消滅の時間をイベント時間として列挙してソートする.
順にみてそのイベントの時間までにどちらの星もまだ消滅していなかったらその時間に消滅したと記録する.

コード


(2586.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

struct event
{
        int u, v;
        double t;
        event(int u, int v, double t):u(u),v(v),t(t){}
        bool operator<(const event &e) const { return t < e.t;}
};

struct star
{
        double x, y, z, vx, vy, vz, r, vr;
};

int n;
vector<event> events;
vector<star> stars;
double die[256];

inline bool valid(double a, double b, double c){ return b*b-a*c+1e-8 > 0;}

double collide_time(const star &s, const star &t)
{
        double x = s.x-t.x, y = s.y-t.y, z = s.z-t.z, r = s.r+t.r;
        double vx = s.vx-t.vx, vy = s.vy-t.vy, vz = s.vz-t.vz, vr = s.vr+t.vr;
        double a = vx*vx+vy*vy+vz*vz-vr*vr;
        double b = x*vx+y*vy+z*vz+r*vr;
        double c = x*x+y*y+z*z-r*r;
        if(!valid(a,b,c)) return -1;

        double p[] = {(-b+sqrt(b*b-a*c))/a, (-b-sqrt(b*b-a*c))/a}, ret = 1e9;
        int f = 0;
        for (int i = 0; i < 2; i++) {
                if(p[i]*s.vr < s.r and p[i]*t.vr < t.r and p[i] > 0) {
                        ret = min(ret, p[i]);
                        f = 1;
                }
        }
        return f? ret: -1;
}

void solve()
{
        for (int i = 0; i < n; i++) {
                star &s = stars[i];
                events.push_back(event(i,i,s.r/s.vr));
                for (int j = i+1; j < n; j++) {
                        double t = collide_time(s, stars[j]);
                        if(t > 0) events.push_back(event(i,j,t));
                }
        }
        sort(begin(events),end(events));

        for(auto &e: events) {
                if(die[e.u] < 0 and die[e.v] < 0){
                        die[e.u] = die[e.v] = e.t;
                }
        }
        for (int i = 0; i < n; i++) {
                printf("%.12f\n", die[i]);
        }
}

void init()
{
        for (int i = 0; i < n; i++) {
                die[i] = -1;
        }
        events.clear();
        stars.clear();
}

bool input()
{
        cin >> n;
        init();
        for (int i = 0; i < n; i++) {
                double x, y, z, vx, vy, vz, r, vr;
                cin >> x >> y >> z >> vx >> vy >> vz >> r >> vr;
                stars.push_back((star){x,y,z,vx,vy,vz,r,vr});
        }
        return n;
}

int main()
{
        while(input()) solve();
        return 0;
}

Comments