ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1388. Photo

Interesting problem..
Posted by [SPbSU ITMO] WiNGeR 21 Feb 2007 03:33
I'm very puzzled with it. Could anybody give me a hint?
Re: Interesting problem..
Posted by Denis Koshman 19 Aug 2008 18:13
One of ideas (didn't implement it yet):

1) sort all trees on their angle (for every bank)
2) for each ray from origin keep only one tree on that ray.
3) rotate a line sequentially - this way you'll get all different captures for each bank at O(N*log(N))
4) perform hashing for images on the other bank so that hash value can be updated at not more than O(log(N)) with each rotation. E.g. base-360 number with angles-to-leftmost-tree as digits can be updated at O(1) with each increment, including consideration of scaling factor.
5) for each image on one bank try to find corresponding image for the other using hash as aid.
6) There is always possible solution 0 (photos of the opposite banks).

Edited by author 19.08.2008 18:15