| ENG RUS | Timus Online Judge |
Discussion of Problem 1388. PhotoShen Yang solution: [1] // Problem 1388. Photo 5 Nov 2017 12:37 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 devil Re: solution: // Problem 1388. Photo 24 Oct 2018 07:52 Edited by author 26.10.2018 10:33 Shen Yang can anyone explain the problem description please? // Problem 1388. Photo 18 Nov 2016 16:48 thanks I want to know what's the task of this problem. GeoSer The projection? // Problem 1388. Photo 15 Feb 2015 14:40 What kind of projection? Orthographic or perspective? Edited by author 15.02.2015 14:43 Sandro (USU) Problem 1388 "Photo" is under investigation (+) // Problem 1388. Photo 7 Oct 2009 11:58 New test by [SPbSU ITMO] WiNGeR was added. The problem was rejudged. New tests will be added soon. [SPbSU ITMO] WiNGeR Interesting problem.. [1] // Problem 1388. Photo 21 Feb 2007 03:33 I'm very puzzled with it. Could anybody give me a hint? Denis Koshman Re: Interesting problem.. // Problem 1388. Photo 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 Walrus Admins! Is test #18 correct? [6] // Problem 1388. Photo 5 Feb 2006 23:52 Walrus Answer me! [5] // Problem 1388. Photo 11 Feb 2006 12:55 There is no error in precision because I used long arithmetics... Safe Bird if there were someone else that come up with a nice algorithm....(-) // Problem 1388. Photo 26 Feb 2006 18:43 Edited by author 03.03.2006 17:15 Vladimir Yakovlev (USU) Re: Answer me! [3] // Problem 1388. Photo 27 Feb 2006 13:51 I don't know :( How can I check this test? You are the only person who tried to solve this problem. Walrus Re: Re: Answer me! [1] // Problem 1388. Photo 1 Mar 2006 16:43 Please, check my program on tests after #18. If it works correctly on theese tests I think test #18 should be deleted :(. Safe Bird you shoud know: // Problem 1388. Photo 1 Mar 2006 18:13 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:) Walrus As I understand, problem was rejudged :). // Problem 1388. Photo 11 Mar 2006 12:21 Ivankov Dmitry 2 Admins, plz correct english text [1] // Problem 1388. Photo 30 Oct 2005 13:07 "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))". Vladimir Yakovlev (USU) Fixed (-) // Problem 1388. Photo 31 Oct 2005 01:50 Safe Bird To ADMIN, Sample Incorrect? [7] // Problem 1388. Photo 25 Oct 2005 17:11 I think for sample2, the correct output should be 2. Am I right? Or please inform me if I misunderstood the description. Thanx. Kit (Vologda SPU) Re: To ADMIN, Sample Incorrect? [6] // Problem 1388. Photo 25 Oct 2005 18:06 It seems, we can take lines y = 1 and x + y = -1. What do you think of it? Safe Bird Can you explain it in details?(haven't understood yet) [5] // Problem 1388. Photo 26 Oct 2005 18:39 Mithril hmm.....i cannot understand either // Problem 1388. Photo 26 Oct 2005 18:59 please . Kit (Vologda SPU) Re: Can you explain it in details?(haven't understood yet) [3] // Problem 1388. Photo 26 Oct 2005 20:34 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? Safe Bird You meant that the film is something like a line with infinity length? [2] // Problem 1388. Photo 26 Oct 2005 21:23 Vladimir Yakovlev (USU) Yes, the film is an infinite line (-) [1] // Problem 1388. Photo 27 Oct 2005 11:58 Safe Bird So the intersections(+) // Problem 1388. Photo 28 Oct 2005 22:14 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 upb_guys why is the answer 4 at the first sample input?? [2] // Problem 1388. Photo 24 Sep 2005 20:37 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 Mithril Re: why is the answer 4 at the first sample input?? // Problem 1388. Photo 29 Sep 2005 08:43 i have the same question .... cannot understand the problem : ( Admin here ? Ivankov Dmitry Projection is strictly described in text // Problem 1388. Photo 29 Sep 2005 09:50
|