Can anyone give me the approach how to deal with this problem ? thanks if you can help me.
whatever program i give i could recive as “run time error” or “time exceed” plz help me
In this problem most important thing to note is that “no 3 lines are coincident”. So if 2 lines cross each other, they will add 1 to number of intersections.
Now you are given lines, which is a list of pairs. Let the pairs be denoted as <L, R>.
Example - for 8 questions ->
(BTW: The image uploader of this site is broken)
Now consider <5, 3>, it cuts all pairs <L, R> where (L < 5 AND R > 3) OR (L > 5 AND R < 3).
So just count the number of intersections for all pairs.
Hope this helps!
1 Like
will it take O(n^2) time as i have to all the pairs in it. will it work ? O(n2) is sufficient for this ? thanks in advance.
will it take O(n^2) time as i have to all the pairs in it. will it work ? O(n2) is sufficient for this ? thanks in advance
@hellodear: Yes it will take O(n^2) time. To determine if it is sufficient, check the bounds. Anyway, you can just code it first. And please be a good boy, and delete the answer which was meant to be a comment.
but, where can i submit it ? it is already closed and i am not finding the question in Peer or easy section. then how to check that it is AC ? please tell
@hellodear: I also searched, but couldn’t find the problem for submission. Maybe you should start a new thread, asking if the BTCD problems will be added to peer section.