Обсуждение @ 1504. Хорошие манеры @ Timus Online Judge

Changes for 1504 "Good Manners" (+)

Послано Vladimir Yakovlev (USU) 30 окт 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" (+)

Послано [SPbSU ITMO] WiNGeR 7 ноя 2006 03:36

I think there is an O(NlogN) solution

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

Послано Vedernikoff Sergey 9 ноя 2006 14:41

I also think so...

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

Послано Sid 22 ноя 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" (+)

Послано EfremovAleksei 22 дек 2006 21:40

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

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

Послано Vit Demidenko 5 янв 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

Обсуждение задачи 1504. Хорошие манеры