just in case thats the code

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

static inline double dot(const double* a, const double* b) { return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]; }
static inline double mind(double a, double b) { return a < b ? a : b; }
static inline double maxd(double a, double b) { return a > b ? a : b; }

static inline bool intersect_ray_sphere(const double* p, const double* dir, const double* sc, double sr, double* t)
{
    const double m[] = {p[0] - sc[0], p[1] - sc[1], p[2] - sc[2]};
    const double b = dot(m, dir), c = dot(m,m) - sr*sr;
    if(c > 0 && b > 0) return false;
    const double discr = b*b - c;
    if(discr < 0) return false;

    *t = maxd(0, -b - sqrt(discr));
    return true;
}

static inline bool intersect_moving_sphere_sphere(const double* c0, double r0, const double* v0, const double* c1, double r1, const double* v1, double* t)
{
    // to transform to moving sphere vs stationery sphere: subtract v1 from both v1,v0
    // to transform to ray-sphere intersection: expand sphere1 by radius of s1

    const double r = r0+r1;
    double v[] = { v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2] };

    double vlen = sqrt(dot(v,v));
    if(vlen < 1e-6) return false;
    v[0] /= vlen, v[1] /= vlen, v[2] /= vlen;

    bool ret = intersect_ray_sphere(c0, v, c1, r, t); *t /= vlen;
    return ret;
}

int main()
{
    unsigned N; double Rd; scanf("%u %lf\n", &N, &Rd);
    double c[N][3], v[N][3];
    for(unsigned i = 0, n = N ; i < n ; ++i) scanf("%lf %lf %lf %lf %lf %lf\n", &c[i][0], &c[i][1], &c[i][2], &v[i][0], &v[i][1], &v[i][2]);

    const double R = Rd / 2.0;

    double min_t; bool have_intersection = false; unsigned min_pair1, min_pair2;
    for(unsigned i = 0, n = N ; i < n ; ++i)
    for(unsigned j = i+1, m = N ; j < m ; ++j)
    {
        double t; bool intersect = intersect_moving_sphere_sphere(c[i], R, v[i], c[j], R, v[j], &t);
        if(intersect && (t < min_t || have_intersection == false))
            min_t = t, min_pair1 = i, min_pair2 = j, have_intersection = true;
    }

    if(have_intersection)   printf("ALARM!\n%.3f %u %u\n", min_t, min_pair1+1, min_pair2+1);
    else                    printf("OK\n");

    return 0;
}

Edited by author 31.07.2016 21:50

Edited by author 31.07.2016 21:51

Edited by author 31.07.2016 22:01

3 1
0 0 0 1 0 0
9 0 0 -1 0 0
5 0 0 -1 0 0
--------------
ALARM!
2.000 1 3

I got AC through

t <- max(0, min(t1, t2))
if t = 0 do nothing

Edited by author 22.11.2013 08:33

I have WA 3. what should i output for this test?
2 1
1.000000000001 0 0 0 0 0
0 0 0 -1 0 0

Could someone give me a hint (or test) to help me to fix WA on test #11?

I have o(n * n) algorithm, not many calculations inside cycle, but still TLE12. Imho, everybody writes such a solutions, but in c++ in can be accepted in 0.015, but i have 1.031 (or more) in java. That's not fairly. I ask autors to increase TL up to 2 seconds, or maybe change your time checking system to prevent this...

ds:=sqr(b)-a*c;

the checking must look like this
if ds+0.000000000001>=0 then
...

Tests aren't really strong in my opinion. I coded a correct (but a little too slow) solution, which gave time limit on test 10. Then I just ignored the cases, where the first object's number is divisible by 7 and it ran in time (1/7 time optimization), and got accepted. But if we have tests, whose answers are 1 x, 2 x, 3 x, ... , 10 x (for example) this solution will fail.

My program passed the tests, published in this thread, but it couldn't passed test 5.
What is in this test?

Edited by author 05.03.2008 20:18

I always have WA.

The idea is simple: get derivative from distance.
assume a1=x[i]-x[j],a2=y[i]-y[j],a3=z[i]-z[j], b1 = vx[i]-vx[j],b2 = vy[i]-vy[j],b3 = vz[i]-vz[j].

Then we should solve quadric equation ax^2+bx+c to find time, where a=a = (b1*b1+b2*b2+b3*b3), b = 2*(a1*b1+a2*b2+a3*b3), c = (a1*a1+a2*a2+a3*a3)-d;

where i'm wrong?

Edited by author 02.03.2008 22:32