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

Vladimir Yakovlev (USU) Changes for 1504 "Good Manners" (+) [5] // Задача 1504. Хорошие манеры 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.

[SPbSU ITMO] WiNGeR Re: Changes for 1504 "Good Manners" (+) [4] // Задача 1504. Хорошие манеры 7 ноя 2006 03:36

I think there is an O(NlogN) solution

Vedernikoff Sergey Re: Changes for 1504 "Good Manners" (+) // Задача 1504. Хорошие манеры 9 ноя 2006 14:41

I also think so...

Sid Re: Changes for 1504 "Good Manners" (+) [2] // Задача 1504. Хорошие манеры 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?

EfremovAleksei Re: Changes for 1504 "Good Manners" (+) [1] // Задача 1504. Хорошие манеры 22 дек 2006 21:40

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

Vit Demidenko Re: Changes for 1504 "Good Manners" (+) // Задача 1504. Хорошие манеры 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. Хорошие манеры