Блог пользователя Chilli

Автор Chilli, 10 лет назад, По-английски

So I've been trying to solve this problem recently.

http://main.edu.pl/en/archive/oi/20/gob

My current solution is this:

For each contiguous dark segment, extend a line that passes through the dark segment's endpoints. The position to place the lantern must lie on all of these lines.

Second, for the walls that are completely illuminated, we can create half planes from that, with which we can find points that can reach all walls. This process will give us a polygon. The position obtained from using the dark segments must lie inside this polygon.

However, I am not satisfied that this is the right solution. Compared to the other problems in this contest, it seems far more difficult to implement. In addition, there seems to be many corner cases involved in this problem as well, leading to an inelegant solution. I fear I have missed an obvious solution, and decided to post here to make sure.

Thanks

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

This problem was meant to be painfully hard to implement (one have to take into account that, although we are assured no three points lie on the same line, after cutting some half-planes this may change). I guess this kind of problems has become popular recently:

http://main.edu.pl/en/archive/oi/21/waz

http://main.edu.pl/pl/user.phtml?op=showtask&task=cza&con=OI22 (currently only in Polish).

So, good luck!

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Talking about geo problem from POI, this one is more fun :D http://main.edu.pl/en/archive/oi/21/lam