simiao's blog

By simiao, history, 9 years ago, In English

The problem I'm talking about is this one http://codeforces.net/gym/100733/problem/J, where you have a set of objects and a set of line segments and you want to maximize the number of objects that have at least one segment above and below itself, by just moving the segments horizontally, and the segments and objects never share the same y coordinate (see the problem for a clearer explanation), initially I thought to simulate moving the objects in steps of 1 on x axis so I would try all possible configurations, but once I read that the x and y coordinates may vary from 0 to 10^6, it would be a TLE answer since I can have 10^3 objects, I've seen a problem similar to this one before and couldn't solve, now again. Can someone help me to understand how to get a AC answer on this kind of problem?

Thanks!!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't this related somehow to Line Sweep?