I copied some of the AC solution (anshal21) and tested on ideone with the test case n=10^5 and n/2 horizontal lines and n/2 vertical lines making a grid with all line segments of maximum possible length. All the solutions are giving TLE or Runtime Error. And when I tested those solutions for n=10^3 or n=10^4, they are working successfully. I researched about this topic on the internet and the best algorithm I found for this was Sweep Line Algorithm and it's time complexity is stated as O(nlogn+k) where k = number of intersection, which in my test case in n^2/4, so this makes it as a O(n^2). And as the constraints are n=10^5. n^2 cannot run in the given time limit. asked 14 Nov '16, 18:40

@yb4singh answered 14 Nov '16, 18:54

My solution is $O(n\log(n))$, I guess most of the others too. Maybe the sweep line algorithm you are referring to has the intersection points as output (then you have to actually all intersections which is obviously at best linear in the number of intersection). We just have to count, which can be done in $O(\log(N)$ per segment using a BIT/Segment tree. As to the "grid testcase": I ran my solution locally on the case generated by
It ran in 0.1s. Codechef servers are typically slower by a factor of 2 or 3, stilll way lower than 1s. I'm not arguing that my solution is optimal written wrt. runtime (is could definitely be improved) but I figured it would be fast enough for codechef. Maybe your testing enviroment is way slower (possibly concerning I/O). answered 14 Nov '16, 19:13

I'm quite sure my solution works in $O(n\log n)$ and does not depend on $k$. I also used a sweep line. answered 14 Nov '16, 18:52

hey anshal answered 14 Nov '16, 18:57
