What is the idea of this problem? Can anybody discuss in detail.
1 Like
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 .
Now repeat same thing for the vertical lines , this time iterate over x and find the answers and in the end sum up all the answers.
now find the number of corner points and subtract them from total answer. you can use BIT or segment-tree for the range query , rest is simple implementation.
P.S. for reference you can see this code , I used BIT for the range query.
3 Likes
You don’t have to repeat same thing for vertical lines, swaping (x,y) and then doing same function will do.
yeah! pretty much same thing 
topcoder has a tutorial talking about this and similar problems…The basic idea is called line sweep algorithm.
1 Like
You can go through this video.Then,you can see its implementation in my code(using Segment tree)https://www.codechef.com/viewsolution/12087104
3 Likes
You have to also keep in mind the segment thing? How are you gys coping with that?
nice video.
1 Like
You can also use square root decomposition for range queries in this problem. My code: https://www.codechef.com/viewsolution/12042756
1 Like
if you encounter a left endpoint of a line segment , add it to your data-structure , if you encounter a right endpoint , remove it .
just as sarvagya said , keep the track of ends
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
1 Like
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.
1 Like
I did the line sweep as mentioned by anshal21 but I used a modified BST instead of segment/BIT tree. Will the segment/BIT tree approach work for higher values of x and y(say 10^9) ??
1 Like
Yes, use coordinate-compression first and then it will reduce to number of points which is 2*10^5.
1 Like
@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?
1 Like
yeah co-ordinate compression is a very good idea I didn’t think of it initially and I thought BST was suitable as I didn’t notice range of x and y.
But should we do coordinate compression twice ??
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?
and we are using 2 scan (vertical and horizontal) coz we need to get it for each of the lines. Please verify?