Show all threads Hide all threads Show all messages Hide all messages | If you got WA#3 or WA#16 | kolesnik_av | 1600. Airport | 24 Jul 2023 18:06 | 9 | ds:=sqr(b)-a*c; the checking must look like this if ds+0.000000000001>=0 then ... Also when I calculated square roots for a*t^2 + 2*b*t + c = 0 as t1,2 = (-b +- sqrt(b^2 - a*c)) / a I had wa3. When I use b = 2.0 * b t1,2 = (-b +- sqrt(b^2 - 4.0*a*c)) / (2.0*a) I got AC. It is very curiously... I has WA#3. Even, i use check ds+0.000000000001>=0. I don't understand what's wrong. :( Can you talk me what in test 3? If ds passes this test, it may be less than zero. so, if it is less than zero, reset it to zero. otherwise, sqrt won't perform as expected. Also check for possible -0.000 replies (that happens in printf("%.3lf") when number is negative, but becomes zero after round-up). Some checkers do not like that. Is negative time a possible answer? :( There is curious fact, that you can get AC with eps = .1! Most important do not forget about: If ds passes this test, it may be less than zero. so, if it is less than zero, reset it to zero. otherwise, sqrt won't perform as expected. I also checked abs(ds) < eps , then t = -b/(2*a) Without it, it was WA3 | getting WA1 but all tests given in "discussion" pass | alexey.orlov | 1600. Airport | 31 Jul 2016 21:50 | 1 | 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 | If you have WA 14 | Ivan Tyamgin (TNU) | 1600. Airport | 13 Apr 2014 20:46 | 1 | 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 | Ignore the root t <= 0 | alex4814 | 1600. Airport | 22 Nov 2013 08:27 | 1 | I got AC through t <- max(0, min(t1, t2)) if t = 0 do nothing Edited by author 22.11.2013 08:33 | check this test please | sich_off (ONPU) | 1600. Airport | 7 Mar 2010 02:19 | 2 | 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 anyone give some tests? | Faeton (Kyiv - Mohyla Academy) | 1600. Airport | 8 Nov 2009 00:10 | 13 | 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 it's right if d = d * d check negative roots be careful with float point try this random test 4 15.0 15.0 1.4 -3.0 3.0 54.0 130.0 65.0 23.0 4.0 5.0 3.0 34.4 23.0 57.0 5.0 8.0 4.0 31.4 7.0 34.0 7.0 123.0 76.0 54.4 ALARM! 0.124 3 4 Edited by author 03.03.2008 04:35 Edited by author 03.03.2008 04:36 Please give me tests when the roots are negative!! it's not hard 2 0.1 0 1 0 1 1 0 0 0 0 1 -1 0 OK roots -0.45 and -0.55 one more test(with positive roots) 2 0.1 -10000 -10000 0 0.1 0.1 0 -10000 10000 0 0.1 0 0 ALARM! 199999.000 1 2 Why we should check negative roots if d = d*d ??? what happen when d==d*d?? Edited by author 04.03.2008 17:24 Why we should check negative roots if d = d*d ??? Edited by author 04.03.2008 17:24 it's right if d = d * d , :) check negative roots what happen when d==d*d?? nothing! I just wanted to say that we should replace d with d*d before calculations Edited by author 04.03.2008 19:51If I`m not mistaken, x in equation ax^2+bx+c is time from the begging...so we shouldn`t check negative roots, because it was before the start point! What`s wrong? I can`t understand... If I`m not mistaken, x in equation ax^2+bx+c is time from the begging...so we shouldn`t check negative roots, because it was before the start point! What`s wrong? I can`t understand... in this case check == ignore we chose smallest positive root you can send me your code I'll check it in this case check != ignore :) Please, give me some hints related to "be careful with float point"? use eps for example if (discriminant<0) continue; // it's wrong if (discriminant+1e-9<0) continue; // it's right Edited by author 06.03.2008 20:41 Thank you! I used #define EPS 0.000000001 if(discr>=-EPS) and had got AC! Edited by author 03.03.2008 23:43 Edited by author 03.03.2008 23:43 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 Don't use this formula. It's not right. Silly author mistake =) | WA on test #11 | sanok | 1600. Airport | 19 Jan 2009 00:43 | 1 | Could someone give me a hint (or test) to help me to fix WA on test #11? | What can be lower bound for speed? For example, can it be 1e-10 :) ? | partisan (Andrey Korotkov) | 1600. Airport | 19 Sep 2008 03:28 | 5 | It's your epsilon for compare or minimum possible speed for object? (Sorry for stupid question if I'm wrong in my suppose) Problem isn't in this. I had crash #8 (Invalid floating point operation) and just find the problem and got AC. This is 'eps' for comparisons (mostly against zero). I don't care about speed, I just find minimum non-negative time. Non-negative means 't > -eps'. Also, right before output I write 'if(t<0) t=0' to protect from -0.000 output. Same thing takes place before 'sqrt' evaluation. | Autors, TL in Java... | HonoraryCoder | 1600. Airport | 19 Aug 2008 04:13 | 3 | 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... I have ACepted this problem in 0.234 using Java without any optimizations. I have 0.234 in C++ with simple O(N^2) algo. Square roots are slow even in C++. | Why WA5 | Beksinski | 1600. Airport | 19 Aug 2008 04:12 | 2 | 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 had it when I checked solutions only for zero discriminant (while should've for any non-negative). If that was your bug too..... :))))))))))) | Weak test set | Alexander Georgiev | 1600. Airport | 8 Mar 2008 06:26 | 1 | 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. |
|
|