Task 103. Количество пересечений

UniLecs

Задача: даны две параллельные прямые, на первой прямой есть N точек, на второй M точек. Каждая точка первой прямой соединена отрезком с каждой точкой другой прямой. Точки расположены таким образом, что кол-во точек пересечений максимально. Необходимо определить максимально возможное кол-во точек пересечения, расположенных между двумя такими прямыми.

Входные данные: N, M - натуральные числа от 1 до 10^3.

Вывод: максимально возможное кол-во точек пересечения.

Пример: N = 2, M = 3

Answer = 3

Идея: рассмотрим сначала частный случай, далее на его основе перейдем к общему случаю. Положим f(N, M) - максимальное кол-во точек пересечения.

Частный случай: очевидно, что f(1, M) = 0. То есть когда на первой прямой всего одна точка, то никакие два отрезка не пересекаются.

Обощаем. Пусть n1, n2, .., nN - точки первой прямой, m1, m2, .., mM - точки второй прямой. Соединим точку n1 с точками m1, m2, .., mM. На отрезке (n1, m1) точек пересечения не будет. Но на след.отрезке (n1, m2) будут лежать точки пересечения с отрезками (m1, n2), (m1, n3), ..., (m1, nN) (всего точек будет N - 1).

Получаем, что на отрезке (n1, mj) будут лежать точки пересечения с отрезками (mi, xk), где i < j, 2 <= k <= N (всего (j - 1) * (N - 1) точек). Т.е. кол-во точек пересечения, ктр лежат на отрезках исходящих из n1 будет равно:

(1 + 2 + ... + (M - 1)) * (N - 1) = (M * (M - 1) / 2) * (N - 1)