GODF's blog

Cut Length
By GODF, history, 5 years ago, In English

Hi. Today i tried to solve 598F - Cut Length. There is an editorial. However as a pupil i did not get anything from that. So any idea would be appreciated how to solve it. Thank you in advance.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

We basically need to find the length of the common part between a line AB and a polygon P.

First for each line XY in polygon P, compute the intersection point between AB and XY.

These are the points where the line either enters the polygon or leaves the polygon.

Sort these points according to their order on the line (based on their distance from A or distance from B).

Your answer is the sum of distance between each Entering point and its immediate next Leaving Point in this order.

This is the basic idea. But the implementation can be quite tricky, since vertex points may occur twice as intersection points and 180-degree angles are allowed in the input. If you can't figure it out on your own, just look into someone else's code.

→ Reply