Ada and Cucumber | Editorial by CodingKnight

Each cucumber is represented as straight line segment extending between its two endpoints **(x1,y1)** and **(x2,y2).** As Ada's house is located at the origin, the solution of the problem is equal to the maximum of such segments which intersect a ray starting at the origin and extending in a particular direction in the polar-angle range **] 0, 2 pi ]**.

Let us assume that a radar-like ray is sweeping such polar-angle rang in the counterclockwise direction starting at angle **0.0**.  Let us assume also that **count** is the number of line segments intersecting the ray at particular angle.

The first observation is that **count** changes only when the ray passes through a line segment end point. As each line segment as two endpoints, the polar angles ** a1** and **a2 ** can be sorted as **b1 = min(a1,a2)** and **b2 = max(a1,a2)** such that **b2 > b1**.

The second observation is that if **b2 - b1 < pi**, then counterclockwise sweeping should increment **count** by one when the sweeping angle reaches **b1**, and decrement it by one when the sweeping angle is increased above **b2**.

The third observation is that if **b2 - b1 > pi**, then counterclockwise sweeping should increment **count** by one at angle **0.0**, decrement it by one when the sweeping angle is increased above **b1**, and finally increment it by one when the sweeping angle reaches **b2**.

A map container can used to store the increments and decrements made to **count** by each of the **N** line segments, where the key of the map is either **b1** or **b2** and the value associated with such key is either incremented or decremented. The condition **above** can be implemented by adding a very small increment *epsilon* to the key **b1** or **b2**. After this preprocessing step, **count** is initialized to **0**, and it is updated by adding the increments stored in the map ordered by the polar angle key. The maximum value of **count** after iterating through all entries in the map is the answer to the problem.

The complexity of this solution is O(N log N).

Ada and Cucumber | Editorial by CodingKnight

Download submission

All caught up!

View submission

Is your resume even shortlisted?