If you sort segments according to INCREASING length.  Then you can consider all segments one by one consecutively.  Find points belong to the current segment.  For those points current segment is the answer.
Because of the segments are sorted.

From all suggested hints, this is the fastest way to do it.
Initially I tried with trees, but I was getting TLE on #13.
Finally I decided to use a map for the points (with key=point, value=index)
It's a very convenient Data Structure, because it provides fast search for the nearest value (lower bound), and allows you to delete that point once its segment has been found.
I tried without deleting it, but got TLE #14.
Deleting each point from the map after finding it makes the map smaller after each iteration.

Finally got an AC in 0.1