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

Обсуждение задачи 1726. Кто ходит в гости…

AC in 0.09 ... a hint
Послано Христо Попов (B&W) 23 ноя 2022 23:21
After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution.
In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :))

The arrays of X and Y coordinates can be sorted independently from each other.

So basically, this input:
3
1 3
2 1
3 2
will have exactly the same result (which is 2) as
3
1 1
2 2
3 3
Re: AC in 0.09 ... a hint
Послано Mr_Ell 16 фев 2023 12:53
can you proof it?
Re: AC in 0.09 ... a hint
Послано Losingways 9 апр 2023 18:52
Assuming a (x1, y1), b (x2, y2), then the distance from c (x3, y3) to (x1, y1) and (x2, y2) is equivalent to the distance from (x1, y2) and (x2, y1)