Герцогиня
Лакей-Лещ вынул из-под мышки огромное письмо (величиной с него самого, не меньше) и передал его Лягушонку.
– Герцогине, – произнес он с необычайной важностью. – От Королевы. Приглашение на крокет.
Лягушонок принял письмо и так же важно повторил его слова, лишь слегка изменив их порядок:
– От Королевы. Герцогине. Приглашение на крокет.
Приключения Алисы в стране чудес (перевод Н.М. Демуровой)
Итак, Герцогиня готовится к королевскому крокету и шьет себе корсет (корсет для крокета). На корсете предусмотрены дырочки для шнуровки, всего N+M дырочек. Расположены они в 2 ряда: в одном ряду N дырочек, а во втором – M.
Шнуровка очень сложная – специальные стяжки соединяют дырочки из первого ряда с дырочками из второго ряда, образуя при этом огромное количество пересечений между рядами. Герцогиня в отчаянии – ей обязательно надо знать это число! Ведь она не желает оскорбить Королеву своим невежеством.
Конечно, Герцогиню симпатичным героем назвать трудно – достаточно взглянуть на портрет «Безобразной Герцогини» художника XVI века Квинтена Массейна. Скорее всего эта Маргарита Маульташ, герцогиня Каринтии и Тироля (XIV в.) и стала прообразом для первых рисунков Герцогини в "Алисе в стране чудес". Однако помочь Герцогине нужно.
Будем считать, что N точек в первом ряду имеют координаты (0,1), (0,2), ..., (0,N), а M точек во втором ряду имеют координаты (1,1), (1,2), ..., (1,M). Некоторые точки с разными абсциссами соединены отрезками, требуется определить, сколько существует различных пар отрезков, которые между собой пересекаются.
Входные данные
В первой строке записаны числа N, M, K, где K – это количество отрезков между точками (1 ≤ N, M ≤ 300, 1 ≤ K ≤ N*M). В последующих K строках записано по два числа X и Y, которые означают, что соединены отрезки с координатами (0,X) и (1,Y). Все отрезки во входном файле различны.
Выходные данные
Выведите количество пар отрезков, которые пересекаются. Если отрезки касаются концами, то это не учитывается за пересечение.