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 1477. Airplanes

Is something wrong with my algorithm?
Posted by upb_guys 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.
Re: Is something wrong with my algorithm?
Posted by Igor E. Tuphanov 28 Sep 2006 18:07
Your algorithm is correct.
Re: Is something wrong with my algorithm?
Posted by Vedernikoff Sergey 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
Re: Is something wrong with my algorithm?
Posted by {AESC USU} Dembel 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."