I was largely defeated by this problem. I hacked an awful convex-hull algorithm, and brute-forced a solution to the small test case. I was interested to look at some of the solutions by the best.
Many of the successful solutions calculate angles between trees using floating point arithmetic expressions based on atan(dx,dy), and compare the angles with expressions like while ( ... && a[r] - a[i] < M_PI - eps) How should eps be set to be large enough to account for all rounding errors, and small enough to distinguish distinct angles? Suppose we have two angles A and B with tan(A) = ax/ay and tab(B) = bx/by. Then when A and B are close, A-B is close to tan(A-B) = (ax/ay-bx/by) / (1+ax.bx/ay.by). Simplify to give tan(A-B) = (ax.by-bx.ay)/(ax.bx+ay.by) In the current question -2N < ax,bx,ay,by < 2N where N=1000000 so by careful choice of ax,ay,bx,by we find the smallest non-zero value of tan(A-B) is about 1/(8.N^2). So if you set eps to 1e-13, then you should be OK. Burunduk1 (rank 1) chose eps = 1e-15, so is safe. Other values used by those ranked in the top 10 include 1e-12, 1e-10 (twice), and 1e-8. All appear to be defeated by a test case of the form 4 0 0 999999 1000000 -999998 -999999 -1000000 1000000 A little luck is useful. I've certainly had it in the past. But in case the GCJ team start using even more test-cases exploring dark corners, be very careful how you set your eps. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/b9f4d273-cef3-4119-8267-a6625265288a%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
