CakeForSix
TCO 2019 Final · 2019-11-14 · by misof
Problem Statement
Time limit is 4 seconds.
You have a cake.
Seen from above, the cake is a (strictly) convex polygon.
You are given the coordinates of its vertices in the
You have five friends. You now want to cut the cake into six pieces of equal area (but not necessarily equal shape). Of course, anyone can do that in five cuts -- but only a true pro can do it in three!
Find three straight-line cuts passing through the same point that cut the cake into six equally large parts. Return {x, y, d1, d2, d3}, where (x, y) is the common point of the three cuts, and d1, d2, d3 are their directions in radians.
Notes
- The positive direction along the x axis is 0 (radians), the positive direction along the y axis is pi/2 (radians).
- A cut in direction d is the same as a cut in direction pi*k+d for any integer k.
- You may return any directions, they do not have to be from [0,pi).
- The grader will compute the areas of your six cake pieces in doubles. The answer will be accepted if the relative or absolute difference between them is less than 10^(-4).
- More precisely, let X and Y be the smallest and the largest of your six areas, as computed by the grader. Then, your answer will be accepted if Y < max( X + 10^(-4), X * (1+10^(-4)) ).
- (The original version of the problem used 1e-7 precision instead of 1e-4. For upsolving this problem in the archive the precision limit was lowered due to the existence of challenge cases that most likely make the task unsolvable with 1e-7 precision. In an ideal world the constraints would not allow such cases and still require high precision, so that it isn't easy to solve the problem via some general numeric optimization.)
Constraints
- x will have between 3 and 50 elements, inclusive.
- y will have the same number of elements as x.
- All coordinates will be between 0 and 10,000, inclusive.
- x and y will describe a convex polygon in counterclockwise order.
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns: {24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
A symmetric but not regular hexagon. The example answer corresponds to cutting it into halves horizontally and making two other cuts through its center that cut each part into thirds.
{0, 1000, 0}
{0, 0, 1000}
Returns: {333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
A right triangle. Again, we can start by making one of the three cuts along its axis of symmetry.
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns: {69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
An irregular pentagon.
{0, 0, 10000, 10000}
{10000, 0, 0, 10000}
Returns: {5000.000000000911, 5000.0, 0.0, 0.9827937232470758, 2.158798930342717 }
{136, 7540, 8392}
{5135, 172, 9154}
Returns: {5355.999999999865, 4820.333333334152, 0.959693619341629, 2.0100309250510993, 3.0813845404188718 }
{300, 400, 300, 200}
{500, 600, 700, 600}
Returns: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
A square, rotated by 45 degrees.
Submissions are judged against all 83 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CakeForSix with a public method vector<double> cut(vector<int> x, vector<int> y) · 83 test cases · 2 s / 256 MB per case