ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1504. Good Manners

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