Chilli's blog

Help with Computational Geometry Problem from Polish Olympiad
By Chilli, 10 years ago, In English

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

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

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So my solution is on the right track?

    Thanks for clarifying.

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply