ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1103. Карандаши и окружности

My algo complexity is O(n^4), Is it exists any more efficient? (-)
Послано Victor Barinov (TNU) 11 май 2005 18:09
Re: My algo complexity is O(n^4), Is it exists any more efficient? (-)
Послано Burunduk1 11 май 2005 20:25
Algo which I wrote is O(n*logn) but also I know O(n) one.

Try to choose one point which will be on the circle. O(1)
Than try to choose another one point which will be on the circle. O(n*logn) or O(n)
Finally build circle by these two points. O(n)

PS: I used such two points that all other points are at one side of the line which contains these two points.
Why!?
Послано Victor Barinov (TNU) 12 май 2005 00:04
I not understand why your algo is right. Maybe we'll discuss some questions by e-mail. Mine is victorbarinov@ua.fm
Thanks!
Re: Why!?
Послано Ripatti [Ufa] 23 ноя 2010 16:45
My simple linear solution uses Inversive geometry.

1. Inverse plane with respect to one of points (let it is A). O(n).
2. Chose another (not A) most left point (let it is B). O(n).
3. Sort all points without A and B with respect to B by polar angle and chose middle (let it is C). We want to get exactly one element on middle place, so I used std::nth_element which work O(n).
4. Output A, B, C. O(1).
Re: Why!?
Послано KNIGHT0X300 10 фев 2013 15:44
I can guarantee that the above algorithm is working. I came up with a similar algorithm :)
Re: Why!?
Послано c_pp 9 янв 2017 20:55
Thx @Ripatti [Ufa].
A solve with O(n) , got AC 0.001s.

Hint for others:
1. did not need any math functions, like  acos, atan.  use simple vector multiplications.
2. calc cos(v[i]) , i>2.  values before sorting.
3. use std::nth_element
4. if need more speed, use buffered i/o.

Good Luck!!