What is the idea of this problem? Can anybody discuss in detail. asked 14 Nov '16, 21:22

just Iterate through every y from 1 to 10^5 and keep the record of live vertical lines for current y and find the answers for the horizontal lines whose y value is equal to current y with range query on the array keeping record of live vertical lines . answered 14 Nov '16, 21:42
You don't have to repeat same thing for vertical lines, swaping (x,y) and then doing same function will do.
(14 Nov '16, 21:53)
yeah! pretty much same thing :P
(14 Nov '16, 22:04)
You have to also keep in mind the segment thing? How are you gys coping with that?
(14 Nov '16, 22:25)
if you encounter a left endpoint of a line segment , add it to your datastructure , if you encounter a right endpoint , remove it .
(14 Nov '16, 23:04)
just as sarvagya said , keep the track of ends
(14 Nov '16, 23:22)
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?
(15 Nov '16, 01:36)
showing 5 of 6
show all

https://www.youtube.com/watch?v=dePDHVovJlE/ You can go through this video.Then,you can see its implementation in my code(using Segment tree)https://www.codechef.com/viewsolution/12087104 answered 14 Nov '16, 22:12
2
nice video.
(14 Nov '16, 22:36)
2
@shukrant.: From vid it is clear that complexity = O(nlogn+R) ..R is O(n^2)...how come it is O(nlogn+R) ?How does hat R part come?
(15 Nov '16, 01:06)
R is used for reporting all the intersections in any segment.We does not require this.
(15 Nov '16, 18:15)

topcoder has a tutorial talking about this and similar problems..The basic idea is called line sweep algorithm. https://www.topcoder.com/community/datascience/datasciencetutorials/linesweepalgorithms/ answered 14 Nov '16, 22:10

You can also use square root decomposition for range queries in this problem. My code: https://www.codechef.com/viewsolution/12042756 answered 14 Nov '16, 22:49

First read about sweep line algo.U can understand it from this http://www.youtube.com/watch?v=dePDHVovJlE U can see in the video that the complexity is O(Nlog N)+R where R is the number of intersections. Suppose you have x horizontal and y vertical lines,maximum number of intersections will be x * y(This is similar to selecting 1 horizontal line and 1 vertical line).U can find maximum number of intersection using A.M>=G.M rule which will be (N * N)/4. Hence just by using Sweep Line algorithm the complexity becomes O(Nlog N)+O(N * N) which is same as O(N * N) which results in TLE.U can refer to this code which got TLEs in 2nd subtask Code : https://www.codechef.com/viewsolution/12084739 Now what shall we do?? ;) U can easily observe that total number of intersection points is basically the sum of intersection points of each individual line divides by 2.We will use this fact to find out the answer.Basically we have to find the answer for each individual line first and then use it to find the number of intersections. Instead of iterating through all the possible values in that range we can use BIT or segment tree to find the answer in O(log N) After that we have to subtract all those points which are end points of both vertical and horizontal lines which can be done by storing those points before calculating. We have to apply sweep line algorithm once for all vertical lines and once for all horizontal lines. This is my final code : https://www.codechef.com/viewsolution/12092468 Feel free to ask questions.Happy coding ;) answered 14 Nov '16, 23:38
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?
(15 Nov '16, 01:45)
Actually I am scanning once but storing the required values in a and b just after scanning the values.For calculating vertical lines I am storing the required values in struct array a and for horizontal lines in struct array b.
(15 Nov '16, 10:38)

Actually there is a almost same problem which was asked in one of the Codeforces round earlier. Just in that problem, you had to change the part regarding the cases when both the intersection occur at the boundaries. For that as per the question, we can see that at a given point maximum of 2 lines can intersect (you can prove it using contradiction: Suppose 3 lines intersect. All 3 can't be horizontal or vertical. Without loss of generality assume 2 are horizontal and 1 is vertical, then again no 2 horizontal lines also share a point. Hence, it is not possible). Thus a simply sort of all the points was enough to remove the last condition. Here is my clean implementation of the solution. Hope the solution is clear and understandable, once the algorithm is clear. answered 15 Nov '16, 00:40
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?
(15 Nov '16, 01:42)
2
Yes. You are correct.
(15 Nov '16, 02:04)
