fourth post:

You can remove most of the special cases by using a binary search instead of finding closed forms in some places. Also, I'm surprised that MIT had to tweak epsilons to get their solution to pass. The data was made to be numerically stable for minor percolations of the input. (WF's makes similar guarantees for its data in the specs of similar problems) Although, maybe the data should have allowed for larger percolations. Do you know what approach they used? Perhaps it compounds error? ReplyContext Matt Fontaine 31.03 09:12 Petr Mitrichev I've implemented exactly the same solution. I didn't calculate the remaining shape, though - just a list of its vertices,more... You don't need to add the points from the square that are inside the polygon. The proof idea is it is not possible to form an area with a hole (open region) by unioning the areas of three overlapping rectangles. Therefore, if you cover the perimeter of the polygon, you cover the whole polygon. :) So the problem reduces to covering a set of lines using three rectangles. ReplyContext Petr Mitrichev 31.03 02:42 Gaoyuan Chen FYI: it is solvable with floating-point, but maybe it is very hard: MIT team tried lots of different eps and passedmore... Thanks for the info! As I only had ~30 minutes for it, I've tried to implement something that doesn't need any hand calculations. Now I found the bug - I was dividing by 2*cur_radius, not by 2*r. After fixing the bug my solution TLEs as expected :) ReplyContext Gaoyuan Chen 31.03 02:36 Petr Mitrichev I've tried the following approach: let's fix one of the enemies who lies on the circle's boundary (since we canmore... FYI: it is solvable with floating-point, but maybe it is very hard: MIT team tried lots of different eps and passed with 11 wrong tries during the contest. UC Berkeley team solved it after contest with floating-point without any wrong try. I haven't read details of your solution yet, but from the feedback of one guy in Berkeley team, it have lots of different cases and need to do lots of calculation by hand. ReplyContext Petr Mitrichev 31.03 02:29 Gaoyuan Chen First we do binary search for the side length of square. And we can proof, one of our up to 3more... I've implemented exactly the same solution. I didn't calculate the remaining shape, though - just a list of its vertices, as that is a bit easier: just intersect the square sides with the polygon sides. One should also add vertices of the square that are inside the polygon, and I was planning to do that, but it passed without doing that :) In order to avoid the confusion about a square covering its own intersection points, I've extended squares by 2*eps when intersecting, and by eps when checking. ReplyContext Gaoyuan Chen 31.03 02:25 Matt Fontaine Gaoyuan, what solution idea did your team try for problem B in the last hour?

http://q99.it/j11Elbp