I_Love_Michelle_Shen's blog

SPOJ Problem GOODG
By I_Love_Michelle_Shen, history, 9 years ago, In English

Anyone can help solve problem problem GOODG? I can't figure out how to apply Convex Hull DP since the lines won't be added in sorted order.

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While you could use convex hull dp to solve this problem, it is unnecessary. Since time is always increasing and you always add new lines to the top, you can just maintain a stack of active lines, deleting them when they become irrelevant.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this problem can be solved using Sweep line algorithm by Bentley-Ottmann. Refer this link: 'http://geomalgorithms.com/a09-_intersect-3.html' for this algorithm. in worst case, no. of intersections can be O(N). when a upper line cross the lower line, then make this upper line inactive. So, when a intersection happens, one line is getting delete. so, max of O(N) intersections can happen in worst.

→ Reply