|
|
Show all threads Hide all threads Show all messages Hide all messages | Page 1 | Idea | InstouT94 | 2166. Two Roads | 16 Mar 2024 20:49 | 1 | Idea 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)). | Hint | Mickkie | 2166. Two Roads | 18 Oct 2023 18:15 | 1 | Hint Mickkie 18 Oct 2023 18:15 Read article: convex hull of n*(n-1)/2 intersection points of n lines Implementation is very easy. But the proof is cool to read. |
Pages: 1 |
|
|