Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Chilli's blog

By Chilli, 5 years ago, ,

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

 » 5 years ago, # |   +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/wazhttp://main.edu.pl/pl/user.phtml?op=showtask&task=cza&con=OI22 (currently only in Polish).So, good luck!
•  » » 5 years ago, # ^ |   0 So my solution is on the right track?Thanks for clarifying.
 » 5 years ago, # |   +8 Talking about geo problem from POI, this one is more fun :D http://main.edu.pl/en/archive/oi/21/lam
 » 5 years ago, # |   0 I love have -10000 in codeforces . I'm police ....