Найти сумму квадратов между всеми парами точек

@071010 · Регистрация: 23.12.2024

Студворк — интернет-сервис помощи студентам

Подскажите, почему не проходит задача. Нужно найти сумму квадратов между всеми парами точек. Вроде делаю все правильно.

На плоскости задано N точек.

Напишите программу, которая найдет сумму квадратов расстояний между всеми парами точек.

Формат ввода

Первая строка ввода содержит единственное натуральное число N (1 ≤ N ≤ 100 000) – количество точек. Последующие N строк содержат по два целых числа X и Y (-10 000 ≤ X, Y ≤ 10 000) – координаты точек.

Формат вывода

Единственная строка вывода должна содержать одно целое число – сумму квадратов расстояний между всеми парами точек.

Пример

Ввод
4
1 1
-1 -1
1 -1
-1 1

Вывод
32

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var
  n,i,j : int64;
  x,y : array[-1000000..1000000] of int64;
  r,sum : int64;
begin
 assign(input,'points.dat');
 reset(input);
 assign(output,'points.sol');
 rewrite(output);
  readln(n);
  for i:=1 to n do  begin
    readln(x[i],y[i]);
  end;
  
  for i:=1 to n-1 do begin
    for j:=i+1 to n do begin
    r:=(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
    sum:=sum+r;
  end;
  end;
  writeln(sum);
  close(input);
  close(output);
end.

@bormant · 31.01.2025, 15:11

Сообщение от Storm Screamer

В Турбо Паскале нет Int64

Нет.
Но выше уже разобрались, что в тестирующей системе TP тоже нет.
Тестирующая система предлагает из подходящего
- FPC 3.2.2 x86,
- Delphi 7,
- PascalABC.NET 3.8.3.

@Storm Screamer · 31.01.2025, 15:27

Для PascalABC.Net.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
program SumOfSquaredDistances;
 
var
  N, i: integer;
  x, y: array of integer;
  sumX, sumY, sumSquares: Int64;
begin
  // Чтение количества точек
  ReadLn(N);
 
  // Инициализация массивов
  SetLength(x, N);
  SetLength(y, N);
 
  // Чтение координат точек
  for i := 0 to N - 1 do
    ReadLn(x[i], y[i]);
 
  // Вычисление сумм
  sumX := 0;
  sumY := 0;
  sumSquares := 0;
 
  for i := 0 to N - 1 do
  begin
    sumX := sumX + x[i];
    sumY := sumY + y[i];
    sumSquares := sumSquares + (Int64(x[i]) * x[i] + Int64(y[i]) * y[i]);
  end;
 
  // Вычисление результата
  WriteLn(N * sumSquares - (sumX * sumX + sumY * sumY));
end.

@Cyborg Drone · 31.01.2025, 16:22

ХОТЯ... avk959, bormant, Storm Screamer... Народ, мне одному кажется, что Вы что-то напутали?

Сейчас проверю.

ФедосеевПавел · 31.01.2025, 19:33

Хороший переход от цикла к произведению суммы.
Пробовал раскладывать и находить последовательно относительно предыдущей суммы квадратов, но так вычислить произведение всех элементов попарно не сообразил.

Теперь, когда решение видно, можно чуть улучшить - это однопроходный алгоритм и сохранение массива ему не нужно - вычисления по мере ввода.

@bormant · 31.01.2025, 21:09

Сообщение от ФедосеевПавел

однопроходный алгоритм и сохранение массива ему не нужно

Кстати да:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
  n, i, x, y, sx, sy: LongInt;
  ss: Int64;
begin
  ReadLn(n);
  for i:=0 to n-1 do begin
    Read(x, y);
    Inc(sx, x);
    Inc(sy, y);
    Inc(ss, Sqr(x) + Sqr(y));
  end;
  WriteLn(ss*n - Sqr(Int64(sx)) - Sqr(Int64(sy)));
end.

@Cyborg Drone · 31.01.2025, 23:46

Проверил.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? S=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left((x_i-x_j)^2+(y_i-y_j)^2 \right)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i-x_j)^2+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(y_i-y_j)^2=S_x+S_y $

Рассмотрим S_x, для S_y будет аналогично.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? S_x=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i-x_j)^2=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i^2+x_j^2-2x_ix_j)=\\=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i^2+x_j^2)-2\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}x_ix_j=\\=(n-1)\sum_{i=1}^{n}x_i^2-2\sum_{i=2}^{n}x_i\left( \sum_{j=i-1}^{n-1}x_j\right)=\\=(n-1)\sum_{i=1}^{n}x_i^2-2\sum_{i=1}^{n}x_iS_i $

где S_i определяется рекуррентным соотношением

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \begin{cases}S_1=0 \\S_i=S_{i-1}+x_{i-1}\end{cases} $

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Cyborg Drone Модератор 10478 / 5772 / 3413 Регистрация: 17.08.2012 Сообщений: 17,536
	31.01.2025, 16:22
	ХОТЯ... avk959, bormant, Storm Screamer... Народ, мне одному кажется, что Вы что-то напутали? Сейчас проверю. 0

ФедосеевПавел Модератор 8675 / 4512 / 1670 Регистрация: 01.02.2015 Сообщений: 13,949 Записей в блоге: 14
	31.01.2025, 19:33
	Хороший переход от цикла к произведению суммы. Пробовал раскладывать и находить последовательно относительно предыдущей суммы квадратов, но так вычислить произведение всех элементов попарно не сообразил. Теперь, когда решение видно, можно чуть улучшить - это однопроходный алгоритм и сохранение массива ему не нужно - вычисления по мере ввода. 1

@Cyborg Drone Модератор 10478 / 5772 / 3413 Регистрация: 17.08.2012 Сообщений: 17,536
	31.01.2025, 23:46
	Проверил. $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> S=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left((x_i-x_j)^2+(y_i-y_j)^2 \right)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i-x_j)^2+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(y_i-y_j)^2=S_x+S_y<br />$ Рассмотрим S_x, для S_y будет аналогично. $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> S_x=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i-x_j)^2=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i^2+x_j^2-2x_ix_j)=\\=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_i^2+x_j^2)-2\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}x_ix_j=\\=(n-1)\sum_{i=1}^{n}x_i^2-2\sum_{i=2}^{n}x_i\left( \sum_{j=i-1}^{n-1}x_j\right)=\\=(n-1)\sum_{i=1}^{n}x_i^2-2\sum_{i=1}^{n}x_iS_i<br />$ где S_i определяется рекуррентным соотношением $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \begin{cases}S_1=0 \\S_i=S_{i-1}+x_{i-1}\end{cases}<br />$ 3