Задача: Cow Curling
В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке
плоскости.
Подсчёт очков в коровьем кёрлинге ведётся следующим образом:
Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
INPUT FORMAT:
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).
* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).
OUTPUT FORMAT:
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B
SAMPLE:
| Ввод |
Вывод |
4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3 |
1 2 |
INPUT DETAILS:
У каждой команды по 4 камня.
Команда A имеет камни (0,0), (0,2), (2,0), (2,2).
Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).
OUTPUT DETAILS:
Команда A захватила камень противника в точке (1,1).
Команда B захватила камни противника в точках (0,2) и (2,2).
Ваш ответ: