Discussion @ 1504. Good Manners @ Timus Online Judge

Changes for 1504 "Good Manners" (+)

Posted by Vladimir Yakovlev (USU) 30 Oct 2006 14:14

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" (+)

Posted by [SPbSU ITMO] WiNGeR 7 Nov 2006 03:36

I think there is an O(NlogN) solution

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

Posted by Vedernikoff Sergey 9 Nov 2006 14:41

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" (+)

Posted by EfremovAleksei 22 Dec 2006 21:40

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

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

Posted by Vit Demidenko 5 Jan 2012 13:32

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

Edited by author 06.01.2012 03:13

Discussion of Problem 1504. Good Manners