match the following problem

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 ->

alt text

(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.