Мехди — умный парень, который хочет положить свои ручки в 2D-коробку. Проблема в том, что у него есть N ручек разной длины, и он хочет проверить, сможет ли он положить ручку Pi в коробку.
Ввод:
Первая строка состоит из T количество наборов входных данных 1 ‹= T ‹= 100.
Во второй строке 3 целых числа 1 ‹= N ‹= 1000, 1 ‹= W ‹= 10000, и 1 ‹= H ‹= 10000, количество ручек, ширина коробки и высота коробки, за которыми следуют N строк с длиной ручки Pi.
Вывод:
Для каждой ручки Pi, если она помещается в поле, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек).
Пример ввода:
2 12 17
21
20
Пример вывода:
НЕТ
ДА
Идея:
Первое, что должно было прийти нам в голову, это мысль о том, что диагональ — это самая длинная часть прямоугольника, так как у нас есть просто 2D-коробка. Итак, мы должны сравнить длину каждого пера с диагональю прямоугольника. Формально должно выполняться соотношение H² + W² › L².
Сложность времени:
У нас есть N запросов, и поскольку ответ на каждый запрос равен O(1), ответ на N запросов будет равен O(N).