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)).