Processing math: 100%

Задача Q. Охота на шушанчиков

Автор:А. Жуплев, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Чтобы наловить шушанчиков, Крокодил Гена отправляется в лес с чемоданом и ружьём, стреляющим усыпляющими дротиками. В лесу он становится в точку с координатами (XG;YG) и начинает внимательно смотреть по сторонам. Как только Гена видит шушанчика, он тут же стреляет в него, и скоро спящий шушанчик оказывается в чемодане Крокодила. Гена всегда стреляет мгновенно и точно.

Лес состоит из N деревьев. На плане i-ое дерево можно представить в виде круга с координатами центра (Xi;Yi) и радиусом Ri. Гена видит все точки с координатами (x,y), такие, что отрезок (x;y)(XG;YG) не пересекает ни одно дерево.

Один шушанчик, гуляя по лесу, пришёл в точку с координатами (XS;YS). Услышав, что Крокодил Гена в лесу, он бросился бежать в нору с координатами (XH;YH). Требуется определить, сможет ли шушанчик добраться до норы так, чтобы Гена его не увидел.

Формат входного файла

Входной файл состоит из K тестов. В первой строке входного файла содержится число K. Далее следуют описания тестов.

Каждый тест описывается числами XSYSXHYHXGYGN, за которыми следуют N троек чисел XiYiRi.

Формат выходного файла

В выходном файле должно содержаться K строк, каждая из которых должна равняться ESCAPE, если шушанчик из соответствующего теста сможет добраться до норы, или CATCH, если не сможет.

Ограничения

1K10

100XS,YS,XH,YH,XG,YG,Xi,Yi100

1Ri100, 0N100

Деревья не пересекаются и не касаются. Позиции Гены, шушанчика и норы различаются и не находятся внутри деревьев.

Все числа во входном файле целые

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2

3 3 5 0 1 1
2
2 2 1
4 1 1

3 3 5 0 2 0
3
2 2 1
4 1 1
10 18 1
ESCAPE
CATCH

0.014s 0.002s 17