mraron's blog

By mraron, history, 8 years ago, In English

Hello,

It's from Innopolis Open, Final Round, 2015-2016, the problem A. I can't approach it, can somebody give me a hint?

Have nice day,

mraron

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When the left end of the segment (segment of length L) moves between coordinate x0 and x0 + 1 (x0 is integer), the covered area changes as a linear function. The sum/difference of slopes is enough to say how it changes.

You should sweep over the given points, updating something when the sweep is over some point or some point is L to the right from the sweep line. This way you will know the area for any placement you want.