I guess that case is sth like a==0(a=-5Nz) ,b!=0 (b= VxNx+VyNy+VzNz)
(I find a check t=c/b instead of t=-b/c by mistake,and got wa)

I'm sure my source code is perfect. But it never passed test #5. Can anyone help me?

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

int main()
{
        double  cx,cy,cz,nx,ny,nz,r,sx,sy,sz,vx,vy,vz,t;
        double  x,y,z;
        double  a,b,c;
        int     hit;
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&cx,&cy,&cz,&nx,&ny,&nz,&r,&sx,&sy,&sz,&vx,&vy,&vz);
        b=nx*vx+ny*vy+nz*vz;
        c=nx*(sx-cx)+ny*(sy-cy)+nz*(sz-cz);
        a=-5*nz;
        if(b*b-4*a*c<-1e-8)
                printf("MISSED\n");
        else if((b+sqrt(b*b-4*a*c))/nz<-1e-8 && (b-sqrt(b*b-4*a*c))/nz<-1e-8)
                printf("MISSED\n");
        else
        {
                hit=0;
                t=(b-sqrt(b*b-4*a*c))/(10*nz);
                if(t>1e-8)
                {
                        x=sx+vx*t;
                        y=sy+vy*t;
                        z=sz+vz*t-5*t*t;
                        if(r-sqrt(pow(x-cx,2)+pow(y-cy,2)+pow(z-cz,2))>1e-8)
                                ++hit;
                }

                t=(b+sqrt(b*b-4*a*c))/(10*nz);
                if(t>1e-8)
                {
                        x=sx+vx*t;
                        y=sy+vy*t;
                        z=sz+vz*t-5*t*t;
                        if(r-sqrt(pow(x-cx,2)+pow(y-cy,2)+pow(z-cz,2))>1e-8)
                                ++hit;
                }
                if(hit)
                        printf("HIT\n");
                else
                        printf("MISSED\n");
        }
        return 0;
}

1e-9 in this problem is OK.

Can somebody give me test cases or just tell me what is the problem in my program:
#include <iostream>
#include <cmath>

using namespace std;

struct vector
{
    double x;
    double y;
    double z;
};


double dist(vector a, vector b)
{
    double d = sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2) + pow(b.z - a.z, 2));
    return d;
}

double find_d(vector v_normal, vector point)
{
    double minus_d = v_normal.x*point.x + v_normal.y * point.y + v_normal.z * point.z;
    return -minus_d;
}

int main(int argc, char * argv[])
{
    vector C, N, S, V;
    double R;
    cin >> C.x >> C.y >> C.z;
    cin >> N.x >> N.y >> N.z;
    cin >> R;
    cin >> S.x >> S.y >> S.z;
    cin >> V.x >> V.y >> V.z;
    double t1, t2;
    double D = find_d(N, C);

    t1 = (double)(N.x * V.x + N.y * V.y + N.z * V.z - sqrt(20 * N.z * (D + N.x * S.x + N.y * S.y + N.z * S.z) + pow(N.x*V.x+N.y*V.y + N.z*V.z, 2))) / (double)(10.0*N.z);
    t2 = (double)(N.x * V.x + N.y * V.y + N.z * V.z + sqrt(20 * N.z * (D + N.x * S.x + N.y * S.y + N.z * S.z) + pow(N.x*V.x + N.y*V.y + N.z*V.z, 2))) / (double)(10.0 * N.z);

    vector hit1, hit2;
    hit1.x = S.x + t1*V.x;
    hit1.y = S.y + t1*V.y;
    hit1.z = S.z + t1*V.z - 5*t1*t1;

    hit2.x = S.x + t2*V.x;
    hit2.y = S.y + t2*V.y;
    hit2.z = S.z + t2*V.z - 5 * t2*t2;

    if (t1 >= 0)
    {
        if (dist(hit1, C) <= R)
        {
            cout << "HIT";
            return 0;
        }
    }

    if (t2 >= 0)
    {
        if (dist(hit2, C) <= R)
        {
            cout << "HIT";
            return 0;
        }
    }
    cout << "MISSED";
    return 0;
}

This is my code:
#include<iostream.h>
#include<math.h>
//ifstream fin("input.txt");
long double cx,cy,cz,nx,ny,nz,r,sx,sy,sz,vx,vy,vz;
int main(){
    cin >>cx >> cy >> cz >>nx >>ny >>nz >>r >>sx >>sy >>sz >>vx
>>vy >>vz;
    cx-=sx;
    cy-=sy;
    cz-=sz;
    long double V=(nx*vx+ny*vy+nz*vz)/sqrtl(nx*nx+ny*ny+nz*nz);
    long double G=-(10*nz)/sqrtl(nx*nx+ny*ny+nz*nz);
    long double L=(cx*nx+cy*ny+cz*nz)/sqrtl(nx*nx+ny*ny+nz*nz);
    if(V*V+2*L*G<0)
    {
        cout << "MISSED\n";
        return 0;
    }
    long double t=(-V+sqrtl(V*V+2*L*G))/G;
    if(t>=0)
        {
            long double xp=vx*t-cx;
            long double yp=-cy+vy*t;
            long double zp=-cz+vz*t-5*t*t;
            if((xp)*(xp)+(yp)*(yp)+(zp)*(zp)<r*r)
                {
                    cout << "HIT\n";
                    return 0;
                }
        }
    t=(-V-sqrtl(V*V+2*L*G))/G;
    if(t>=0)
        {
            long double xp=-cx+vx*t;
            long double yp=-cy+vy*t;
            long double zp=-cz+vz*t-5*t*t;
            if((xp)*(xp)+(yp)*(yp)+(zp)*(zp)<r*r)
                {
                    cout << "HIT\n";
                    return 0;
                }
        }
    cout << "MISSED\n";
    return 0;
}

This problem does NOT have any special cases. It is just a formula and its CAREFUL implementation.

1) i had wa35 with eps = 1e-15
2) i had wa82 with eps = 1e-11
3) ac with simple eps = 1e-9

help me! =) i can't even conjecture where can mistake be.

1. in the equation a*t^2+b*t+c=0, consider this case: a=0.

2. maybe you will get two positive value of t, and you should check both of them, because the dart will go through the plane twice.

I got AC after getting Crash & WA for the reasons above.

I found it out after submitting my solution and getting 'Accepted'. My solution always says MISSED in the case of the same plane (i was lazy to consider this case in detail)

Edited by author 09.03.2008 14:23

As for Me, the current statement of this problem declares that in both cases, either the dart flies through the target in its plane (0 0 0 0 1 0 1   2 0 0 -1 0 10) or it flies touching the target (0 0 5 0 0 1 1   1 0 0 -1 0 10), the answer must be the same! Not the "MISSED" in the first case and the "HIT" in the second one!

[AC code deleted by me))))]

There was only misprint. Good luck.

Edited by author 14.03.2006 23:37

1. if the dart just touch the target. HIT !!!
   the situation b*b-4*a*C=0

2. if the trace is just on the plain. Always MISSED !!!!

in test #56 dart always situated in dartboard's plane.

Const Zero=1E-9;
Var
 a, b, c, d, r,
 cx, cy, cz,
 sx, sy, sz,
 nx, ny, nz,
 vx, vy, vz: Double;

Procedure Taxis(t:Double);
 Var
  mx, my, mz: Double;
 Begin
  If t < 0 Then Exit;
  mx := sx + vx * t;
  my := sy + vy * t;
  mz := sz + vz * t - 5 * sqr(t);
  If Sqr(mx - cx) + Sqr(my - cy) + Sqr(mz - cz) < Sqr(r) Then
   Begin
    WriteLn('HIT');
    Halt;
   End;
 End;

Begin
 Read(cx, cy, cz, nx, ny, nz, r, sx, sy, sz, vx, vy, vz);
 a := -5 * nz;
 b := vx * nx + vy * ny + vz * nz;
 c := (sx - cx) * nx + (sy - cy) * ny + (sz - cz) * nz;
 If Abs(a) < Zero
  Then If Abs(b) < Zero
        then Begin
              If Abs(c) < Zero Then
               Begin
                writeln('HIT');
                Halt;
               End;
             End
        Else Taxis(-c / b)
  Else Begin
        d := Sqr(b) - 4 * a * c;
        If (d >= 0) or (Abs(d) < 1E-16) Then
         Begin
          d := Sqrt(d);
          Taxis((-b - d) / 2 / a);
          Taxis((-b + d) / 2 / a);
         End;
       End;
 WriteLn('MISSED');
End.

The old tests were quite weak. Thanks to anus(USU) for new tests.

Problem has been rejudged, 271 authors lost AC verdict.

Edited by author 14.12.2006 11:56

<upset> this nice problem have so worse tests.
I hope in paulo-post-future it will be fixed.

Edited by author 05.11.2006 14:14

Should we out "HIT" if:
1) The dart hits the board right on the boundary?
2) The dart hits the board at the T=0?

What are the limitations? (Is double enough?)
What EPS is enough for us?

I'm just tired of having WA11 :(

Edited by author 01.09.2005 23:40

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

double Cx,Cy,Cz,Nx,Ny,Nz,R,Sx,Sy,Sz,Vx,Vy,Vz;
double A,B,C,D;
double l,m,n;
double x,y,z;
double vec,dist;
double a,b,c,dd,t,t1,t2;

double distance(double x,double y,double z,double x1,double y1,double z1) {
 double rez;
 rez=sqrtl(pow(x-x1,2)+pow(y-y1,2)+pow(z-z1,2));
 return rez;
}

int main()   {
 #ifndef ONLINE_JUDGE
    freopen("1093.in","r",stdin);
    freopen("1093.out","w",stdout);
 #endif
 scanf("%lf %lf %lf",&Cx,&Cy,&Cz);
 scanf("%lf %lf %lf",&Nx,&Ny,&Nz);
 scanf("%lf",&R);
 scanf("%lf %lf %lf",&Sx,&Sy,&Sz);
 scanf("%lf %lf %lf",&Vx,&Vy,&Vz);
 //---------------
 A=Nx;B=Ny;C=Nz;
 D=-(A*Cx+B*Cy+C*Cz);
 //-----------------
 a=-5*C;
 b=A*Vx+B*Vy+C*Vz;
 c=A*Sx+B*Sy+C*Sz+D;
 if (fabs(a)<0.0000001) {
  if (fabs(b)<0.0000001) {printf("MISSED"); return 0;}
  t=-c/b;
  x=Sx+Vx*t;
  y=Sx+Vy*t;
  z=Sx+Vz*t-5*t*t;
    if (distance(x,y,z,Cx,Cy,Cz)<R-0.000001) {printf("HIT"); return 0;}
    else {printf("MISSED"); return 0;}
 }

 dd=b*b-4*a*c;
 if (dd<0) {printf("MISSED");return 0;}

 dd=sqrtl(dd);
 t1=(-b+dd)/(2*a);
 t2=(-b-dd)/(2*a);
 if ((t1<0) && (t2<0)) {printf("MISSED");return 0;}

 //printf("dd=%lf\n",dd);
 //printf("t=%lf\n",t);
 if (t1>=0) {
    x=Sx+Vx*t1;
    y=Sx+Vy*t1;
    z=Sx+Vz*t1-5*t1*t1;
    if (distance(x,y,z,Cx,Cy,Cz)<(R-0.000001)) {printf("HIT"); return 0;}
  }

 if (t2>=0) {
    x=Sx+Vx*t2;
    y=Sx+Vy*t2;
    z=Sx+Vz*t2-5*t2*t2;
    if (distance(x,y,z,Cx,Cy,Cz)<(R-0.000001)) {printf("HIT"); return 0;}
  }

 printf("MISSED");
 return 0;
 #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
 #endif
}