|
|
Show all threads Hide all threads Show all messages Hide all messages | solution: | Shen Yang | 1388. Photo | 24 Oct 2018 07:52 | 2 | suppose the slope of line on the x>0 is k ,and slope of (0,0) to n points is k1,k2,...kn then intersection point of x1==1/(k1-k),x2=1/(k2-k)...xn=1/(kn-k) then we choose (x4-x1)/(x2-x1)==(x4'-x1')/(x2'-x1') and (x3-x2)/(x3-x4)==(x3'-x2')/(x3'-x4') we multiply these two equations guess what happens, yes: k is offset then we can get (k4-k1)*(k3-k2)/((k2-k1)*(k3-k4))==(k4'-k1')*(k3'-k2')/((k2'-k1')*(k3'-k4')) en.. this convert to string matching prolems,so suffix array can solve it Edited by author 26.10.2018 10:33 | can anyone explain the problem description please? | Shen Yang | 1388. Photo | 18 Nov 2016 16:48 | 1 | thanks I want to know what's the task of this problem. | The projection? | GeoSer | 1388. Photo | 15 Feb 2015 14:40 | 1 | What kind of projection? Orthographic or perspective? Edited by author 15.02.2015 14:43 | Problem 1388 "Photo" is under investigation (+) | Sandro (USU) | 1388. Photo | 7 Oct 2009 11:58 | 1 | New test by [SPbSU ITMO] WiNGeR was added. The problem was rejudged. New tests will be added soon. | Interesting problem.. | [SPbSU ITMO] WiNGeR | 1388. Photo | 19 Aug 2008 18:13 | 2 | I'm very puzzled with it. Could anybody give me a hint? 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 | Admins! Is test #18 correct? | Walrus | 1388. Photo | 11 Mar 2006 12:21 | 7 | There is no error in precision because I used long arithmetics... Edited by author 03.03.2006 17:15 I don't know :( How can I check this test? You are the only person who tried to solve this problem. Please, check my program on tests after #18. If it works correctly on theese tests I think test #18 should be deleted :(. everyone EXCEPT you don't know how to solve this problem. they could not check whether the cases are right, since there is no more submission! i hope you can share us with your algorithm, then, we can help you check it:) | 2 Admins, plz correct english text | Ivankov Dmitry | 1388. Photo | 31 Oct 2005 01:50 | 2 | "and trees in front of it are centrally projected onto the point (0,0) of the film" Point (0,0) is not on the film. So it should be like that "...are centrally projected onto the film (center is point (0,0))". Fixed (-) Vladimir Yakovlev (USU) 31 Oct 2005 01:50 | To ADMIN, Sample Incorrect? | Safe Bird | 1388. Photo | 28 Oct 2005 22:14 | 8 | I think for sample2, the correct output should be 2. Am I right? Or please inform me if I misunderstood the description. Thanx. It seems, we can take lines y = 1 and x + y = -1. What do you think of it? Trees on the upper side (y > 0) are centrally projected on a line y = 1. Trees on the lower side are centrally projected on a line x + y = -1 (or x + y = -4, if you wish). After scaling both films will be same. But I can't imagine how it can be solved :(((. Any ideas? So the intersections of 1.film (infinity line) 2.the line connecting (0,0) and some points are what that would be projected. Edited by author 02.11.2005 19:30 | why is the answer 4 at the first sample input?? | upb_guys | 1388. Photo | 29 Sep 2005 09:50 | 3 | why is the answer 4 at the first sample input?? how is the projection made? i was thinking that the film is infinite long somewhere behind (0, 0) point and parallel with Ox axis. Edited by author 24.09.2005 20:40 i have the same question .... cannot understand the problem : ( Admin here ? |
|
|
|