Must have been a good 4000 example cases for me, or just bad for the five people I passed in the system tests.

[TheFaxman: looks like the plan of running systests until I win is working out. Keep up the good work!]]]>

- Find a point inside (similar fractal-like search pattern)

- Binary search in a few directions to approximately (something like +/- 0.04) find some edges and make an initial polygon (convex hull).

- Estimate the possible reduction in error available by splitting each existing edge, then split the juiciest one using binary search. Also estimate the expected reduction in error of refining the location of a "known" point on the convex hull and refine that instead of splitting if it was juicier.

- Keep splitting and refining until I run out of samples

- Each point on the convex hull is actually an interval with a sample point known to be outside and a sample point known to be inside. Using this I estimate the area using a weighted average of the inside and outside limits of each point (3/4 outside + 1/4 inside seems to work well).

- At this point I am still pretty consistently underestimating the area (by about 0.1) so, I then add the median error observed by running lots of tests. I fit a function to the number of samples for this. I probably should have fit it to the area and number of samples (subtracting any samples wasted finding the polygon at the start).

The main data structure is just an ordered vector of "points" on my estimated convex hull, where a "point" is actually two points as mentioned above.

Most of the thinking and coding went into estimating the error reduction expected by refining an edge into two, and estimating the most extreme location of the expected but unknown actual polygon vertex, using the neighboring "points" on the convex hull. The final code ended up being pretty simple. I tried some edge tracking in the last couple of days, but I couldn't get it to improve my score.

For reasons of simplicity early on I started using four initial points for the convex hull, planning on trying three later, but never got back to actually try that. I tried eight at one point when had a tricky test case with the first point way in a very acute corner of a small polygon. It fixed that case but made everything else worse so it was quickly abandoned. Not trying three initial points probably cost me.

It was clear from the beginning that with the scoring specified in the rules the performance with few sample points would totally dominate the final score. So I never put any effort into anything that took lots of samples.

Provisional score: 2484.76 (getting the next few points looked really hard, although trying starting with a triangle and calculating the median error differently would have probably helped a bit, maybe got me into the top 10, but I was burning out by then)]]>

from this point with some BS. search 3 points on the perimeter of the polygon. This is a triangle. take each side, take the middle, and try to do an other triangle with BS on the height going outside of the triangle you are searching on. and so on.

I think I have a bug... because this just got: 2222.07. I did some tests.. and I putted some if's and made my score 2239.]]>

Btw. that image really shows well how you pin-point the polygon.]]>

Yep, I did that, too, and agree completely. Seeing how the boundary of forbidden area could suddenly grow beyond the square it was formerly confined to was instructive and seeing how my triangulation method suddenly walks backwards was invaluable.]]>