I used scanline to solve this problem. This method is shown
here: http://e-maxx.ru/algo/length_of_segments_union. All the given points are put in array with 2n+m elements, each point having one of 3 types: start of a segment(0), end of a segment(2), a point for which the answer is needed (1). Then the array is sorted, and we go througth its elements: if the element has type 0, then we insert according segment into the set, if the element has type 2, then we delete according segment from the set, if the element has type 1 then we take the segment of minimum length from set in O(1), and output its id. The complexity is O((2n+m)log(2n+m)) (quicksort).

Edited by author 09.02.2016 14:53

Stack can be used in place of set, reducing time to about 0.148 sec

Edited by author 29.05.2017 14:16