ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 102. Бинарный и тернарный поиск > задача:


Макс и высокая кухня

Задачи раздела

• Все любят уравнения
• Забор
• Ларьки
• Левый двоичный поиск
• Лес и поле
• Макс и высокая кухня
• Правый двоичный поиск
• Принтеры
• Сердечко
• Станция

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/3000/3000/3000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и высокая кухня
Макс и высокая кухня
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

А гренка в нашем ресторане называется крутон. Это точно такой же поджаренный кусочек хлеба. Только гренка не может стоить 8 долларов, а крутон — может.
— О чём говорят мужчины

Что вы знаете про высокую кухню? Макс, например, знает про неё всё! Побывав в ресторане удостоенном звезды «Мишлен» он узнал, что блюдо будет считаться элитным, если перед подачей нарисовать соусом на тарелке многоугольник определённой формы.

Макс перенёс все $$$N$$$ точек многоугольника на лист бумаги, с определённой на нём декартовой системой координат, отмечая точки в порядке обхода. Вернувшись домой Макс увидел, что у него есть только круглые тарелки радиуса $$$R$$$.

Определите, сможет ли Макс разместить указанный многоугольник на тарелке с радиусом равным $$$R$$$?

Входные данные

Первая строка содержит целое число $$$T$$$ ($$$1 \le T \le 10$$$) — количество наборов входных данных. Далее следуют описания наборов данных.

Первая строка каждого набора входных данных содержит целое число $$$N$$$ ($$$3 \le N \le 100$$$) — количество точек в многоугольнике.

Следующие $$$N$$$ строк содержат координаты точек многоугольника. Каждая из них содержит целые числа $$$X_i$$$ и $$$Y_i$$$ ($$$-1000 \le X_i, Y_i \le 1000$$$) — координаты по осям абсцисс и ординат соответственно.

Следующая строка содержит вещественное число $$$R$$$, записанное не более чем с 6 знаками после десятичной точки ($$$0 \le R \le 3000$$$) — радиус тарелки.

Выходные данные

Выведите $$$T$$$ строк. В каждой из них выведите «YES», если в соответствующем тесте Макс сможет разместить многоугольник на тарелке и «NO», если не сможет. Выводите результаты без кавычек.

Пример

Входные данные
3
5
-1 -1
2 -1
2 2
0 1
-1 2
4.0
3
0 0
3 7
1 5
3.2
5
0 0
5 -5
10 0
8 5
2 5
5.5
Выходные данные
YES
NO
YES

Для отправки решений необходимо выполнить вход.

www.contester.ru