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

Обсуждение задачи 1775. Космический боулинг

hint
Послано ASK 1 апр 2018 01:37
For each pair of points, consider the family of lines parallel to the line that connects the points. Project all the points on the line perpendicular to the family, sort the coordinate, and find the smallest coordinate distance that covers k points.
Re: hint
Послано ASK 1 апр 2018 17:19
Note that since at least one line on the border must contain two points, instead of sorting one can use partition and nth_element. That is the time complexity does not need logarithm: O(n^3).