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

Обсуждение задачи 1477. Самолёты

Самолеты(1477)
Послано svr 20 дек 2006 10:21
Slow Ac O(N^3*log(N))
O(N^2) -choice plane through two poins and the centre;
O(N*log(N)) -searching semicircle with max number of points
How make more quickly?
Re: Самолеты(1477)
Послано Vedernikoff Sergey 11 янв 2007 15:48
To AC it I've used some analog of hash tables when applied second of your algos (O(N^2)). If points A and B are between two points that we check (on a small arc), then we may not check them in the future. Such a trick helped me to AC the problem in 0.14 secs.