Is the answer to Logging to find the number of triangles made by triples of other trees that each tree is strictly inside? Sounds very inefficient. Would love to hear some insight on this whilst I wait for the official analysis :)
Paul Smith [email protected] On Sun, Apr 19, 2015 at 11:17 AM, john.smith <[email protected]> wrote: > 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. > -- 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/CAJej63Ju7pyf2s0RraBBy2H_2JdJG%2BFLmfyV2TUC4p4sTndS_w%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
