In the wake I publish tasks from the Algorithm track (classic sports programming. In an hour and a half, you need to solve three problems in Java, C #, C ++ or Python.)
1. Pie for six
Formulation of the problem
The time limit is 4 seconds.
You have a pie. Seen from above, the pie has the shape of a (strictly) convex polygon. You are given the coordinates of the vertices in X and Y integers.
You have five friends. You want to divide the cake into six pieces of equal area (but not necessarily the same shape). Of course, anyone can do it in five cuts, but only a pro can do it in three cuts.
Find three cuts in straight lines through one point, which will divide the pie into six equal parts. Print {x, y, d1, d2, d3}, where (x, y) is the common point of all three cuts, and d1, d2, d3 are the cut direction angles in radians.
DefinitionClass: CakeForSix
Method:cut
Parameters: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(be sure your method is public)
Notes
- The positive direction along the x-axis is 0 (radian), the positive direction along the y-axis is pi/2 (radian).
- Slicing in the d direction is the same as slicing in the pi*k+d direction for any integer k.
- You can output any directions, they don't have to be from [0, pi).
- The grader will calculate the areas of your six cake slices 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 largest of your six graded areas. Then your answer will be accepted if Y
- (In the original version of the problem, a precision of 1e-7 was used instead of 1e-4. To address this issue in the archive, the precision limit was lowered due to the presence of call cases that would most likely make the problem unsolvable with a precision of 1e-7. In an ideal world of constraints do not allow such cases and still require high precision, so it is not easy to solve the problem with some general numerical optimization.)
Restrictions
- x contains from 3 to 50 elements inclusive.
- y contains the same number of elements as x.
- all coordinates between 0 and 10 000 inclusive
- x and y define a convex polygon in a counterclockwise direction.
Original in English
Problem Statements
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 int[]sx and y.
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.
Definition
Class: CakeForSix
Method:cut
Parameters: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(be sure your method is public)
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.
Examples
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symmetrical, but not a regular hexagon. An example answer corresponds to cutting it in half horizontally and making two other cuts in the center, which divide each part into three parts.
1)
{0, 1000, 0}
{0, 0, 1000}
Returns:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Right triangle. Again, we can start with one of the three cuts along the axis of symmetry.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Irregular pentagon.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returns: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Square rotated 45 degrees.
[]
Only registered users can participate in the survey. , you are welcome.
I solved the problem for
-
in less than 10 minutes
-
10-30 minutes
-
30-60 minutes
-
1-2 hours
-
more than 2 hours
-
other
42 users voted. 47 users abstained.
Source: habr.com