Intersecting Red and Blue Line Segments

Revision en2, by simiao, 2016-07-22 05:01:27

Hello, I am trying to solve this problem on SPOJ, where is given a set of red lines and blue lines and you have to count the red/blue intersections. My code uses line sweep technique. Initially I was getting a TLE, then I started to use this set. Now I am getting WA veredict.

My idea is: I create 3 kinds of events: — 0 — x of a start of horizontal line — 1 — x of a vertical line — 2 — x of a end of horizontal line then I sort the events, maintaining a set of active horizontal lines (their y's). When I get to a type 1 event (vertical line) I add to the answer the number of horizontal lines in the active set that are intersecting with the vertical line.

Can anybody tell if it's my idea or my implementation and give me some light please :D Thanks!

Tags geometry, line sweep

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English simiao 2016-07-22 05:01:27 432 Tiny change: ' of events\n - 0 - ' -
en1 English simiao 2016-07-22 04:31:39 529 Initial revision (published)