10790. Сколько точек пересечения?

Имеются две параллельные прямые. На одной из них выбрано a точек, на другой – b точек. Любые две точки с разных прямых соединены отрезком. Точки на прямых выбраны так, что количество точек пересечения образованных отрезков максимально. Вычислить это количество точек пересечения.

Вход. Каждая входная строка содержит два числа a и b (0 £ a £ 20000, 0 £ b £ 20000). Обработка данных заканчивается, когда a = b = 0.

Выход. Для каждого теста вывести в отдельной строке его номер и максимально возможное количество точек пересечения отрезков. Результат каждого теста помещается в 64 – битовое число без знака.

Пример входа	Пример выхода
2 2 2 3 3 3 0 0	Case 1: 1 Case 2: 3 Case 3: 9

РЕШЕНИЕ

геометрия + комбинаторный подсчет

Анализ алгоритма

Обозначим через f(a, b) искомое количество точек пересечения. Очевидно, что f(1, b) = 0, так как при a = 1 никакие два отрезка не пересекаются:

Рассмотрим общий случай. Пусть x₁, x₂, …, x_a – точки на первой прямой, y₁, y₂, …, y_b – точки на второй прямой. Соединим точку x₁ с точками y₁, y₂, …, y_b. На отрезке x₁y₁ точек пересечения не будет. На отрезке x₁y₂ будут лежать точки пересечения с отрезками y₁x₂, y₁x₃, …, y₁x_a (всего a – 1 точек). На отрезке x₁y_j будут лежать точки пересечения с отрезками y_ix_k, где i < j, 2 £ k £ a (всего (j – 1) * (a – 1) точек). Количество точек пересечения, которые лежат на отрезках исходящих из x₁, равно (0 + 1 + 2 + … + (b – 1)) * (a – 1) = b * (b – 1) / 2 * (a – 1).

Итак, из f(a, b) точек b * (b – 1) / 2 * (a – 1) точек лежат на отрезках исходящих из x₁, а остальные точки лежат на отрезках с концами в x₂, …, x_a. Имеем рекуррентное соотношение:

f(a, b) = b * (b – 1) / 2 * (a – 1) + f(a – 1, b)

Развернув его, получим:

f(a, b) = b * (b – 1) / 2 * (a – 1) + f(a – 1, b) =

b * (b – 1) / 2 * (a – 1) + b * (b – 1) / 2 * (a – 2) + f (a – 2, b) = ... =

b * (b – 1) / 2 * (a – 1) + b * (b – 1) / 2 * (a – 2) + ... + b * (b – 1) / 2 * 1 =

b * (b – 1) / 2 * a * (a – 1) / 2

Таким образом, максимальное количество точек пересечения равно

*

Пример

Рассмотрим второй тест, для которого a = 2, b = 3. Максимально возможное количество точек пересечения отрезком равно 3 и показано на рисунке:

Реализация алгоритма

Читаем входные данные и для каждого теста вычисляем результат по выше приведенной формуле. При заданных ограничениях на a и b в умножении переполнения не будет, если вычисления проводить в 64-битовом целочисленном типе.

cs = 1;

while(scanf("%lld %lld",&a,&b), a + b > 0)

{

res = a * (a - 1) * b * (b - 1) / 4;

printf("Case %d: %lld\n",cs++,res);

}

Java реализация

import java.io.*;

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int cs = 1;

while(true)

{

long a = con.nextLong();

long b = con.nextLong();

if (a + b == 0) break;

long res = a * (a - 1) * b * (b - 1) / 4;

System.out.println("Case " + cs++ + ": " + res);

}

}

}