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 1588. Jamaica

What is the best algorithm?
Posted by asdsdf 1 Nov 2007 12:42
I use O(n^3), but i meet time  problem. Can you help me?
Re: What is the best algorithm?
Posted by LittlePig 1 Nov 2007 14:32
Of course, the best complexity is O(N^2 log N), but O(N^3) can get AC.
Re: What is the best algorithm?
Posted by EugeneE 17 Dec 2008 21:17
Can anybody in short explain how to create O(N^2 logN) algorithm, please?

I've already accepted O(n^3) solution and there's no promlem with it(definitely not the best implementation of this algorithm got ac in 0.2 sec), but how to create O(N*NlogN) algo?
Re: What is the best algorithm?
Posted by Abzal 22 Aug 2011 05:53
Use angle sort, after use binary search.
Re: What is the best algorithm?
Posted by Enigma [UB of TUIT] 28 Sep 2011 13:07
I've Accepted O(N*NlogN) :)
Re: What is the best algorithm?
Posted by [MAI] iLoveDiscreteAnalysis 10 Feb 2012 18:12
N^2 * log(N^2) algo:

1) Sort n^2 lines by distance.
2) Iterate from largest to smallest.
3) We have to add line to the answer, if we not have bigger line in set, covering this. We can easily check it with set.
Re: What is the best algorithm?
Posted by Andrew Sboev [USU] 26 Mar 2013 21:13
O(N^3) easily gets AC in 0.078s.