ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 2166. Two Roads

Posted by InstouT94 16 Mar 2024 20:49
I haven't coded my idea yet, but it looks plausible. We can use the idea of binsearch by answer. For a fixed cost x, we need to check that all intersection points are inside a square with center (0;0) and side length x*sqrt(2), rotated at an angle of 45 degrees. That is, there are no points of intersection of lines outside the square. Let us cut out the area of intersection with the square for each straight line, then each straight line will be divided into no more than two parts. Then we apply the idea of solving problem 1469. And the complexity will be O(log(max_answer)*n*log(n)).