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

Задача . Cow Curling


Задача

Темы: Многоугольники. Выпуклые оболочки

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке плоскости.
Подсчёт очков в коровьем кёрлинге ведётся следующим образом: Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
PROBLEM NAME: curling
Формат входных данных
* Строка 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).


Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B
Примечание
Команда A захватила камень противника в точке (1,1). Команда B захватила камни противника в точках (0,2) и (2,2).


Примеры
№Входные данныеВыходные данные
1 
4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3
 
1 2
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет