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

Задача . Tied Down


Задача

Темы: Вычислительная геометрия

Беси одна из тех коров, которые любят создавать проблемы. Во избежание этого Фермер Джон решил привязать Беси к изгороди длинной веревкой. Если смотреть сверху, изгородь представляет N столбов (1 <= N <= 10), которые расположены вдоль вертикальной прямой. Беси находится в позиции (bx,by) находящейся справа от это вертикальной линии. Веревка, которой ФД привязывает Беси описывается последовательностью из M отрезков прямой, (3 <= M <= 10,000), где первый отрезок начинается в позиции Беси, и последний отрезок заканчивается в позиции Беси. Никакой из столбов не лежит ни на одном из этих отрезков. Однако отрезки могут пересекаться, и многие отрезки могут пересекаться в своих конечных точках.
Пример такой сцены, вид сверху:

Чтобы помочь Беси освободиться, подружки стащили пилу из амбара. Определите минимальное количество столбов, которые они должны спилить, для того, чтобы Беси могла освободиться (то есть она сможет убежать, И никакой из отрезков веревки не зацепился, ни за какой из столбов)
Все (x,y)-координаты на вводе (столбы изгороди, Беси, конечные точки отрезков), есть целые числа в диапазоне 0..10,000. Все столбы имеют одну и ту же x-координату, bx больше этой величины.
PROBLEM NAME: tied
Формат входных данных
* Строка 1: Четыре целых числа, разделенных пробелами: N, M, bx, by.
* Строки 2..1+N: Строка i+1 содержит разделенные пробелами x и y координаты столба i.
* Строки 2+N..2+N+M: Каждая из этих M+1 строк содержит, по очереди, x и y координаты точки веревки. Первая и последняя точки всегда совпадают с координатами Беси (bx,by).
Формат выходных данных
* Строка 1: Минимальное количество столбов, которое нужно удалить, Чтобы корова смогла убежать, двигаясь вправо.
Примечание
Удаление столба 1 или столба 2 приводит к желаемому результату.


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

Ваш ответ

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


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

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