Changes for 1504 "Good Manners" (+)

Problem statement was updated:

• "All the pieces have distinct coordinates and lie on a table"

• "Coordinates should be precise up to 7 digits"

New tests have been added.

Timelimit was decreased to 3 seconds.

Submissions made after contest have been rejudged.

This problem suppose O(N^2) solution now.

Re: Changes for 1504 "Good Manners" (+)

I think there is an O(NlogN) solution

Re: Changes for 1504 "Good Manners" (+)

I also think so...

Re: Changes for 1504 "Good Manners" (+)

Posted by

Sid 22 Nov 2006 23:07

But how??? I solved this problem using quadro trees. My solution is about O(N^2*log(N)). What is O(N^2) or O(Nlog(N)) algo?

Re: Changes for 1504 "Good Manners" (+)

Diagram of Voronoy - is O(n*log(n))

Re: Changes for 1504 "Good Manners" (+)

O(n^3) is also acceptable, but it seems to be O(n^2)

*Edited by author 06.01.2012 03:13*