Flatland Fidget Spinner
Time limit2sMemory limit512 MB
Given the pixel colors a camera recorded of a three-armed spinner, recover the camera's position and rotation angle.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Implementation, Math
- Solved
- No attempts yet
Problem
Freddy the Flatland photographer wants to write about new toys for the newspaper Flatland Financial Times. He saw a very nice picture of a fidget spinner in the magazine Flatland Weekly, and he likes it so much that he wants to publish the same picture. Flatland copyright law forbids copying the picture, so Freddy decides to take his own picture that looks exactly the same. Help him place his camera.

Photography in Flatland
Freddy owns one 1MP camera and a few cheaper cameras with fewer pixels. One pixel records three real numbers between and as a colour. In the picture Freddy wants to reproduce, the fidget spinner lies on a fully black background. Fully black pixels make up at most of the picture. The spinner is never cut off, so the leftmost pixel and the rightmost pixel are always fully black. The arms of the spinner have pure colours, in counter clockwise order red , green and blue . Every arm has length , and two neighbouring arms are separated by the same angle , that is degrees. The spinner stands in the Origin Photography Studio with its middle at , and the tip of its blue arm at , .

A camera with pixels and viewing angle captures the angle in total, so one pixel covers the angle . The camera sits at position , and the angle is the counter clockwise angle between the positive -axis and the centre of the camera view. The colour of a pixel is the average over the angular range that the pixel covers. Each arm adds its own colour in proportion to the part of that range where the arm is the object closest to the camera. Arms hide each other. Where two arms overlap in the same direction, only the one nearer to the camera is recorded.
The camera in the figure above has pixels and a viewing angle of degrees, so one pixel covers degrees. One pixel of that picture contains both the red arm and the blue arm. Inside that pixel blue covers degrees and red covers degrees, so the pixel records the colour , a shade of purple.
Input
The first line contains the camera properties: the number of pixels () and the viewing angle () in radians.
Each of the next lines contains three real numbers , and () with . The pixels are given in clockwise order. Every real number in the input has at most digits after the decimal point.
Output
Print , and (), the position of the camera and its rotation in radians, separated by single spaces. Print all three numbers with exactly four digits after the decimal point.
Exactly one camera placement produces the given picture, and each of the three printed values stays far from a rounding boundary, so the answer is unique.