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.

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 03:31:53 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

We basically need to find the length of the common part between a line

ABand a polygonP.First for each line

XYin polygonP, compute the intersection point betweenABandXY.These are the points where the line either

entersthe polygon orleavesthe polygon.Sort these points according to

their order on the line(based on their distance fromAor distance fromB).Your answer is the sum of distance between each

Entering pointand its immediate nextLeaving Pointin this order.This is the basic idea. But the implementation can be quite tricky, since

vertex pointsmay occurtwiceas intersection points and180-degree anglesare allowed in the input. If you can't figure it out on your own, just look into someone else's code.