A question on USACO 2019 Open Contest, Silver, Problem 2

Revision en1, by yosako, 2021-12-28 01:15:31

I got stuck at this problem while trying to learn sweep line technique. I've read the editorial for that problem and got seriously confused at the "y coordinate for a segment" part. Like ... how can we compare the y coordinate when a segment consist of two points ? (Apparently I think it has something to do with sorting points by increasing x coordinate, but can't figure out why ...). Also why do we only check for intersection with the "above" segment in the active set when we first meet the beginning of a segment, but check for both the "above" and "below" when we meet a segment's end ? Please explain all of my question in details if possible.

P/s : Remember that I have 2 questions ...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English yosako 2021-12-28 10:38:59 7 Tiny change: 'ns ...\n\nThere's ' -> 'ns ...\n\nEdit:\nThere's '
en3 English yosako 2021-12-28 10:09:59 58
en2 English yosako 2021-12-28 10:09:23 2505 Tiny change: 'ke mistake and improve. ' -> 'ke mistakes to improve. '
en1 English yosako 2021-12-28 01:15:31 878 Initial revision (published)