Yet another triangle week

The first November week included the fifth stage of the 2016-17 Open Cup, the Grand Prix of Siberia (problems, results, top 5 on the left). Team Havka-papstvo dominated the proceedings, and topped the cake with the only passing solution for the very tedious problem 10 - congratulations!

I'd like to highlight the interactive problem 3, which turned out to be the second most difficult. The judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle). There are two steps to solving this one: figuring out how to do it, and then figuring out how to do it in such a way that the implementation isn't a nightmare :)

In my previous summary, I've described another triangle problem: you are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.

The solution is surprisingly straightforward: we find the convex hull of the given points, and then try all triangles with vertices from the convex hull to determine the largest one. It is correct because it's not hard to see that when we fix 2 out of 3 vertices of the triangle, the third one needs to be as far from that line as possible, which means it's a farthest point in some direction, which means it's a vertex of the convex hull. And it is fast enough because it turns out that a set of random points has only O(logn) points on average on its convex hull (see this paper).

Thanks for reading, and check back soon for the next week's summary!

Tweet