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

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

Accepted simple way how to compute sum of distances
Послано Gleb Dubosarskii 6 май 2017 21:52
After sorting of array of x and y all you need to do is to compute this two double sums sum(i=1)^n sum(j=1)^(i-1) (x_i-x_j) and sum(i=1)^n sum(j=1)^(i-1) (y_i-y_j). After simplifications one can obtain that they equal
sum(i=1)^n x_i*(2*i-1-n) and sum(i=1)^n y_i*(2*i-1-n).
After computations you divide final sum by C_n^2=n*(n-1)/2 and get required answer.
Re: Accepted simple way how to compute sum of distances
Послано hduads2020_19321111 29 мар 2021 20:43
Can you make your Formulations readable?