×

# URBANDEV query about the idea

 2 1 What is the idea of this problem? Can anybody discuss in detail. asked 14 Nov '16, 21:22 0★a____ 79●11 accept rate: 20%

 6 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. answered 14 Nov '16, 21:42 4★anshal21 606●8 accept rate: 7% 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) anshal214★ You have to also keep in mind the segment thing? How are you gys coping with that? (14 Nov '16, 22:25) a____0★ if you encounter a left endpoint of a line segment , add it to your data-structure , 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) anshal214★ 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) a____0★ showing 5 of 6 show all
 6 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 4★shukrant 121●4 accept rate: 22% 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) a____0★ R is used for reporting all the intersections in any segment.We does not require this. (15 Nov '16, 18:15) shukrant4★
 2 topcoder has a tutorial talking about this and similar problems..The basic idea is called line sweep algorithm. https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ answered 14 Nov '16, 22:10 537●1●8 accept rate: 27%
 2 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 469●5●29 accept rate: 7%
 2 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 6★likecs 3.7k●22●79 accept rate: 9% 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) a____0★ 2 Yes. You are correct. (15 Nov '16, 02:04) likecs6★
 2 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) ?? answered 15 Nov '16, 00:42 6★sdssudhu 1.1k●3●10 accept rate: 15% 2 Yes, use coordinate-compression first and then it will reduce to number of points which is $2*10^5$. (15 Nov '16, 01:00) likecs6★ 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 ?? (15 Nov '16, 01:09) sdssudhu6★ 2 Yes, twice. (15 Nov '16, 02:05) likecs6★
 0 Here is my solution with sweep line + BIT, runs in 0.25 ms, I hope this can be helpfull. answered 15 Nov '16, 11:58 3★eteruel 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,310
×66

question asked: 14 Nov '16, 21:22

question was seen: 1,712 times

last updated: 15 Nov '16, 18:16