Олимпиадный тренинг

Задача . D. Игра с треугольниками


Даже маленькому Джону нужны деньги, чтобы купить дом. Но он недавно потерял работу; как же он теперь заработает деньги? Конечно, играя в игру, которая дает ему деньги в качестве награды! Ну, может быть, не в те игры, о которых вы думаете.

На плоскости есть \(n+m\) различных точек \((a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)\). Изначально ваш счет равен \(0\). Чтобы увеличить свой счет, вы можете выполнить следующую операцию:

  • Выберите три различные точки, которые не лежат на одной прямой.
  • Увеличьте свой счет на площадь треугольника, образованного этими тремя точками.
  • Затем удалите три точки с плоскости.
Пример игры, где операция выполняется дважды.

Пусть \(k_{\max}\) — максимальное количество операций, которое можно выполнить. Например, если нельзя выполнить эту операцию ни разу, то \(k_\max\) равно \(0\). Кроме того, определим \(f(k)\) как максимальный возможный счет, который можно получить, выполнив операцию ровно \(k\) раз. Здесь \(f(k)\) определено для всех целых чисел \(k\), таких что \(0 \le k \le k_{\max}\).

Найдите значение \(k_{\max}\) и найдите значения \(f(x)\) для всех целых чисел \(x=1,2,\ldots,k_{\max}\) независимо.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le {3 \cdot 10^4}\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n,m \le 2 \cdot 10^5\)).

Вторая строка каждого набора входных данных содержит \(n\) попарно различных целых чисел \(a_1,a_2,\ldots,a_{n}\) — точки на \(y=0\) (\(-10^9 \le a_i \le 10^9\)).

Третья строка каждого набора входных данных содержит \(m\) попарно различных целых чисел \(b_1,b_2,\ldots,b_{m}\) — точки на \(y=2\) (\(-10^9 \le b_i \le 10^9\)).

Гарантируется, что сумма \(n\) и сумма \(m\) по всем наборам входных данных не превышают \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных, учитывая, что максимальное количество операций равно \(k_{\max}\), вы должны вывести не более двух строк:

  • Первая строка содержит значение \(k_{\max}\);
  • Вторая строка содержит \(k_{\max}\) целых числа, обозначающих \(f(1),f(2),\ldots,f(k_{\max})\). Вы можете опустить эту строку, если \(k_{\max}\) равно \(0\).

Обратите внимание, что в условиях этой задачи можно показать, что все значения \(f(x)\) являются целыми числами, не превышающими \(10^{16}\).

Примечание

В первом наборе входных данных есть \(1+3=4\) точки \((0,0),(0,2),(1,2),(-1,2)\).

Можно показать, что вы не можете выполнить две или более операций. Значение \(k_{\max}\) равно \(1\), и вас просят только о значении \(f(1)\).

Вы можете выбрать \((0,0)\), \((-1,2)\) и \((1,2)\) в качестве трех вершин треугольника. После этого ваш счет увеличивается на площадь треугольника, которая равна \(2\). Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно \(2\). Следовательно, значение \(f(1)\) равно \(2\).

В пятом наборе входных данных есть \(8+2=10\) точек.

Можно показать, что вы не можете выполнить три или более операций. Значение \(k_{\max}\) равно \(2\), и вас просят о значениях \(f(1)\) и \(f(2)\).

Чтобы максимизировать счет с помощью только одной операции, вы можете выбрать три точки \((198\,872\,582,0)\), \((-1\,000\,000\,000,2)\) и \((1\,000\,000\,000,2)\). Затем три точки удаляются с плоскости. Можно показать, что максимальное значение вашего счета после выполнения одной операции равно \(2\,000\,000\,000\). Следовательно, значение \(f(1)\) равно \(2\,000\,000\,000\).

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

  • Выберите три точки \((-509\,489\,796,0)\), \((553\,177\,666,0)\) и \((-1\,000\,000\,000,2)\). Три точки удаляются.
  • Выберите три точки \((-400\,714\,529,0)\), \((564\,040\,265,0)\) и \((1\,000\,000\,000,2)\). Три точки удаляются.

Тогда счет после двух операций становится \(2\,027\,422\,256\). Можно показать, что максимальное значение вашего счета после выполнения ровно двух операций равно \(2\,027\,422\,256\). Следовательно, значение \(f(2)\) равно \(2\,027\,422\,256\).


Примеры
№Входные данныеВыходные данные
1
5
1 3
0
0 1 -1
2 4
0 100
-100 -50 0 50
2 4
0 1000
-100 -50 0 50
6 6
20 1 27 100 43 42
100 84 1 24 22 77
8 2
564040265 -509489796 469913620 198872582 -400714529 553177666 131159391 -20796763
-1000000000 1000000000
1
2
2
150 200
2
1000 200
4
99 198 260 283
2
2000000000 2027422256
Статистика успешных решений по компиляторам
 Кол-во
С++3