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

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

Условие

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

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

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

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

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

Каждый тест описывается числами XS YS XH YH XG YG N, за которыми следуют N троек чисел Xi Yi Ri.

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

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

Ограничения

1 ≤ K ≤ 10

 − 100 ≤ XS, YS, XH, YH, XG, YG, Xi, Yi≤ 100

1 ≤ Ri ≤ 100, 0 ≤ N ≤ 100

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

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

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

Входной файл (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.104s 0.010s 17