| ENG RUS | Timus Online Judge |
Обсуждение задачи 1388. ФотографияShen Yang solution: [1] // Задача 1388. Фотография 5 ноя 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: // Задача 1388. Фотография 24 окт 2018 07:52 Edited by author 26.10.2018 10:33 Shen Yang can anyone explain the problem description please? // Задача 1388. Фотография 18 ноя 2016 16:48 thanks I want to know what's the task of this problem. GeoSer The projection? // Задача 1388. Фотография 15 фев 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 (+) // Задача 1388. Фотография 7 окт 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] // Задача 1388. Фотография 21 фев 2007 03:33 I'm very puzzled with it. Could anybody give me a hint? Denis Koshman Re: Interesting problem.. // Задача 1388. Фотография 19 авг 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] // Задача 1388. Фотография 5 фев 2006 23:52 Walrus Answer me! [5] // Задача 1388. Фотография 11 фев 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....(-) // Задача 1388. Фотография 26 фев 2006 18:43 Edited by author 03.03.2006 17:15 Vladimir Yakovlev (USU) Re: Answer me! [3] // Задача 1388. Фотография 27 фев 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] // Задача 1388. Фотография 1 мар 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: // Задача 1388. Фотография 1 мар 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 :). // Задача 1388. Фотография 11 мар 2006 12:21 Ivankov Dmitry 2 Admins, plz correct english text [1] // Задача 1388. Фотография 30 окт 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 (-) // Задача 1388. Фотография 31 окт 2005 01:50 Safe Bird To ADMIN, Sample Incorrect? [7] // Задача 1388. Фотография 25 окт 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] // Задача 1388. Фотография 25 окт 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] // Задача 1388. Фотография 26 окт 2005 18:39 Mithril hmm.....i cannot understand either // Задача 1388. Фотография 26 окт 2005 18:59 please . Kit (Vologda SPU) Re: Can you explain it in details?(haven't understood yet) [3] // Задача 1388. Фотография 26 окт 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] // Задача 1388. Фотография 26 окт 2005 21:23 Vladimir Yakovlev (USU) Yes, the film is an infinite line (-) [1] // Задача 1388. Фотография 27 окт 2005 11:58 Safe Bird So the intersections(+) // Задача 1388. Фотография 28 окт 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] // Задача 1388. Фотография 24 сен 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?? // Задача 1388. Фотография 29 сен 2005 08:43 i have the same question .... cannot understand the problem : ( Admin here ? Ivankov Dmitry Projection is strictly described in text // Задача 1388. Фотография 29 сен 2005 09:50
|