| ENG RUS | Timus Online Judge |
Discussion of Problem 1477. AirplanesShen Yang problem description said plane is at most 15km height from earth surface // Problem 1477. Airplanes 26 Apr 2018 08:42 in fact,we must regard plane is exactly on the surface of the earth so that we can get ac... pperm Test 16 incorrect? [1] // Problem 1477. Airplanes 14 Aug 2010 18:05 I think that test 16 have at least two codirectional vectors. Sandro (USU) Re: Test 16 incorrect? // Problem 1477. Airplanes 16 Aug 2010 12:02 Incorrect test is fixed. Thank you. upb_guys Is something wrong with my algorithm? [3] // Problem 1477. Airplanes 26 Sep 2006 23:42 My algorithm is as follows: I consider planes that cut the sphere in half - they are determined by two points in the input and the center of the sphere. I split the input points in three sets according to this plane - points "above" the plane (say N1 points), points "under" the plane (say N2 points) and points in the plane (all of them being on one circle). Obviously at this moment these points on this circle are not visible since they aren't on the open emisphere, so I try to move this emisphere just a little to make the maximum number of points visible. To handle this, I find the maximum number of points P on some semi-circle. So I conclude that the maximum number of visible points using this plane is the maximum between N1+P and N2+P. Can you give me a case for which this algorithm is not correct? I get WA on test-case 7. Thanks. Igor E. Tuphanov Re: Is something wrong with my algorithm? [2] // Problem 1477. Airplanes 28 Sep 2006 18:07 Your algorithm is correct. Vedernikoff Sergey Re: Is something wrong with my algorithm? [1] // Problem 1477. Airplanes 10 Nov 2006 13:10 Try these tests: Input #1: 1 0 0 1 Output #1: 1 Input #2: 3 0 0 1 0 0 100 0 0 600 Output #2: 3 {AESC USU} Dembel Re: Is something wrong with my algorithm? // Problem 1477. Airplanes 9 Oct 2007 21:25 Test #2 is incorrect, isn't it? "There is not more than one plane at each point of the Earth's surface." Alias (Alexander Prudaev) why sample output is not 5? // Problem 1477. Airplanes 22 Mar 2007 22:50 i don't understand the problem. i think, if to keep far away enought we can see any five of points i am right? svr Самолеты(1477) [1] // Problem 1477. Airplanes 20 Dec 2006 10:21 Slow Ac O(N^3*log(N)) O(N^2) -choice plane through two poins and the centre; O(N*log(N)) -searching semicircle with max number of points How make more quickly? Vedernikoff Sergey Re: Самолеты(1477) // Problem 1477. Airplanes 11 Jan 2007 15:48 To AC it I've used some analog of hash tables when applied second of your algos (O(N^2)). If points A and B are between two points that we check (on a small arc), then we may not check them in the future. Such a trick helped me to AC the problem in 0.14 secs.
|