## Editorial for Back From Summer '19 P4: Wesley And Cake

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

For all subtasks, we can observe that the largest axis-aligned square will always share an edge with the border of the cake. This is because as you move away from the centre the distance between two slopes will always be increasing, thus allowing a square that did not touch the border to be moved towards the border without crossing any cuts. It can also be shown that the cuts are symmetrical about the line .

For the first subtask, we can see that when , there is always a square of side length that does not intersect the cut.

When , we can see that there are two cases. The first is when both slopes have the same sign. In this case, once again there is always a square of side length that does not intersect the cut. The second case is when the two slopes have opposite signs. In this case, we can see that the two lines create four different regions (though only two are distinct due to symmetry). In order to find the largest square in each of the regions, we need to find a line parallel to the border such that the distance from the line to the border is equal to the distance between the two given slopes at that line. This can be done by solving the linear equation where is the side length of the square and are the give slopes. This equation will handle the case where the square shares an edge with the vertical border. To handle the horizontal border, we can take the negative reciprocal of the slopes and use a similar equation.

Time Complexity: Time Complexity: 