开发者

Given n line segments on the plane which are either vertical or horizontal. How to count intersections between these line segments?

开发者 https://www.devze.com 2023-04-05 16:16 出处:网络
I have seen solutions involving sweeping line methods. But I need a divide and conquer method. Basically i want to know if we divide the plane vertically into two subplanes and then try to solve the q

I have seen solutions involving sweeping line methods. But I need a divide and conquer method. Basically i want to know if we divide the plane vertically into two subplanes and then try to solve the questions on both planes, do we have to take some special step in merging?

Would there be any special advantage of using divide and conqu开发者_Go百科er in this problem ?


The only special steps would be handling vertical lines on the division line, and breaking divided horizontal line segments.

0

精彩评论

暂无评论...
验证码 换一张
取 消