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; } I couldn't pass fifth test too, and I had mistake described above. Maybe, there is another mistake in your program. The test 5 in TIMUS is the case when the trace of dart only touches the dartboard in one point (i.e. like the parabola touches the plane). When I had understood this fact I got AC. Edited by author 21.03.2009 17:26 Edited by author 21.03.2009 17:26 So if it touches the plane should we consider it as a hit? My solution also fails WA#5 and I don't understand why... any hints guys? 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 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. Agree!I had suppose I would get "Wrong Answer" several times,but I got "Accepted" at the first submit. it has 2 special cases. to get ac you should guess that touching surface of the target is "hit", but touching it's border is "missed". 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 considered this 2 cases and even the case: b=0, but anyway I got WA 6 again :( t can be only positive? OMFG! So stupid mistake))) Now I've got 'AC' Thank you :D 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 Yes! As for me I considered this case and got WA on 56 test =)) I think the problem isn't correct about this case... Edited by author 13.09.2008 22:28 Edited by author 13.09.2008 22:28 Edited by author 13.09.2008 22:28 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 Edited by author 14.03.2006 23:37 Test11: dart trace is tangent a target. I have some problem with this test, becouse in condition nothing to say about precision of input data. When I changed eps from -7 to -15 I got AC. Dmitry "Logam" Kobelev [TSOGU] test // Problem 1093. Darts 17 Jun 2008 19:14 If you have wa11 try this test. It helped me. 0 0 500 0 0 -913 500 0 0 0 1 0 100 HIT 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. Read rule 5: To hit the dartboard the dart should hit it strictly inside boundary from any side. This is your mistake. Check the conditions of hit in your code one more time. Good luck! Thank you vary much! I got Accepted. To Sandro(USU): Well, well it seems to me that there is a little bit of misunderstanding. First I thought that if the dart trajectory belongs to the plane (and that's exactly the test 56), it can be a hit, if it crosses the circle. Turns out not, in that case it's always MISSED... I do agree that such way the problem is easy to solve. But it can become much tougher, if you change the statement a little bit - to check if the dart crosses the circle, IF the dart is on the plane (infinite number of points). In that case you will have to solve the polinomial not of the 2-nd, but of the 4-th degree (a much more formidable task)... Such a test would be a nice one. I understand that it may not be compatible with the statement for someone, but it would become then a really good problem even for sophisticated programmers... Edited by author 29.12.2006 18:30 Edited by author 29.12.2006 18:30 To SPIRiT: The problem statement is OK for test 56. If you change the statement it will be another problem. It's better to save this problem and make a new one about intersection parabola and circle. You can do it. :) 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 Could you please tell what kind of tests were added? 1. Can the dart now be moving in the same plane where the circle is situated? If so, should we consider the hit? 2. If the dart hits just the boundary - not the inner part, is it a hit or not? 3. What about the precision - for calculation of the equation roots? Is Real type enough in pascal. Or should I use double? Read the problem statement. It is a hit if and only if the dart hits inner part of the board (both in the case of the same plane and another case). Double type is enough for all calculations in this problem. Correct solution should not have problems with precision. <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 I can't agrea with you.... I think it is a very stupid problem :-( It not geometry, only mathematics and any more that. 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 I got AC. Turned out I forgout about D=0. But these questions (especially about limitations) should be mentioned in the statement. I think. #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 } Maybe anyone knows what the test #3? Because I cannot find the mistake in my code. Edited by author 23.06.2005 18:36 When you calculate x,y,z u must use Sx,Sy,Sz but you use only Sx |
|