eolymp
bolt
Try our new interface for solving problems
Məsələlər

Этот пас пройдет

Этот пас пройдет

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Тесса - старшеклассница, которая играет в футбольной команде. Ее тренеры стараются научить технике прохода, а именно хотят помочь игрокам научиться распознавать, когда товарищ по команде открыт для паса. Они решили смоделировать поле квадратной сеткой, как показано ниже. Каждый игрок (нападения или защиты) занимает одну клетку сетки - нападающие игроки обозначены числами, а защищающиеся - черными кругами. Каждый игрок защиты имеет возможность переместиться в любую соседнюю клетку для того чтобы перехватить пас; клетки, которые охраняют защитники, показаны X. Предположим, что игрок 1 владеет мячом. Другой игрок считается открытым, если отрезок, соединяющий центр квадрата этого игрока с центром квадрата игрока 1, не касается ни одного из квадратов, до которых могут дотянуться защитники. Если отрезок касается области защитника даже в одной точке, пас может быть перехвачен. Нападающие игроки никогда не блокируют пасы другим игрокам нападения.

В этом примере Игрок 1 может передать пас игроку 2, но не игрокам 3 и 4.

Образовав такую модель, тренера вдруг неожиданно поняли что они не умеют писать код, который способен определить кто из игроков открыт а кто нет. Один из игроков сообщил им Ваше имя как компьютерного гения, поэтому Вам придется все уладить.

Giriş verilənləri

Состоит из нескольких тестов. Каждый тест начинается с четырех натуральных чисел r c o d, задающих количество строк (r), колонок (c) на сетке и количество нападающих и защищающихся игроков (o и d соответственно). Оба r и c не более 50. Каждая из следующих o строк задают строку и колонку - положение игрока нападения (строки и колонки нумеруются с 0). Далее следуют аналогичные d строк для игроков защиты. Нападающие игроки пронумерованы 1, 2, 3, ... в порядке, в котором они подаются на входе, игрок нападения 1 владеет мячом. Никакие два игрока не находятся в одной клетке сетки. Строка с четырьмя нулями завершает входные данные.

Çıxış verilənləri

Для каждого теста выведите его номер и список игроков, которым игрок 1 может сделать пас мячом. Числа следует выводить в возрастающем порядке, разделяя одним пробелом. Нумеруйте каждый тест как показано в примере.

Nümunə

Giriş verilənləri #1
7 7 4 2
5 1
6 5
0 1
0 6
2 0
4 5
2 5 2 1
0 0
0 4
1 2
1 4 4 0
0 0
0 1
0 2
0 3
0 0 0 0
Çıxış verilənləri #1
Case 1: 2
Case 2:
Case 3: 2 3 4