ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1600. Airport

getting WA1 but all tests given in "discussion" pass
Posted by alexey.orlov 31 Jul 2016 21:50
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