Vasiljko's blog

By Vasiljko, history, 7 years ago, In English

Given convex polygon with N points (clockwise and there are no 3 collinear points). Also given M vertical line segments. Find out how many edges of polygon are intersected by at least one line segment.
Note that if line segment is going through one of the N points, then both edges are counting.

Points are represented as Xi Yi.
Line segments are represented as Ai Pi Ki which means that starting point is at (Ai,Pi) and ending point is at (Ai,Ki)

3 <= N <= 10^5
1 <= M <= 10^5
-10^7 <= Xi,Yi,Ai,Pi,Ki <= 10^7
TL: 1s
ML: 64MB

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Sort edges by smaller x coordinate, and sort vertical lines by x coordinate then do two pointer method to check how many intersect.