Давид поступил программистом на работу в "КБ-1580", занимающимся разработкой робота "Голиаф".
Давид получил первое задание. Описание задания:
- Необходимо переместить "Голиафа" из "начальной точки" в "финальную точку" одним из K представленных способов
так, чтобы "финальная точка" находилась в кольцевов зоне "R" (задается центром и двумя радиусами)
- "начальная точка" и "финальная точка" - точки плоскости, заданные с помощью значений абсциссы и ординаты
(x, y) - координаты начальной точки; (xx, yy) - координаты "финальной точки"
- каждый из K способов перемещения задается с помощью набора чисел Ai
Если набор состоит из \(a_n,a_{n-1},\dots,a_1\). то "финальная точка" вычисляется
как результат выражения\(a_n\cdot f(x,y,n)+a_{n-1}\cdot f(x,y,n-1)+a_1\cdot f(x,y,1)\)
- \(f(x,y,n)= (x,y)\) при n=1, для любых x,y
- \(f(x,y,n) =f(x,y,n-1)*(x,y)\)
- операция * (умножение точек) определяется так
\((a,b)*(c,d)=(a\cdot c-b\cdot d,a\cdot d+b\cdot c)\)
где \(\cdot,+,- \) обычные арифметические операции
- умножение числа на точку(радиус-вектор) определяется так:
\(a\cdot(x,y)=(a,0)*(x,y)=(ax,ay)\) (то есть это просто умножение координат)
- сложение точек (радиус-векторов) определяется так:
\((x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)\)
Введенные операции позволяют рассматривать число как "точку на оси абсцисс", то есть считать \(a=(a,0)\),
а значит \(a\cdot(x,y)*(x,y)+b\cdot(x,y)=(a\cdot(x,y)+b)*(x,y)=(a\cdot x+b,a\cdot y)*(x,y)\),
что позволяет применить схему Горнера
для вычисления \((xx,yy)=a_n\cdot f(x,y,n)+a_{n-1}\cdot f(x,y,n-1)+a_1\cdot f(x,y,1)\)
Итак, Давиду, доступно:
- (x,y) - координаты "начальной точки"
- (mx,my) - координаты центра целевой зоны "М"
- R1,R2 - радиусы целевой зоны "R" (зона "R" - кольцевое пространство между двумя концентрическими окружностями)
- \(A_1,\dots,A_K\) - наборы чисел, определяющие перемещение "Авроры"
Давид
должен определить:
- количество наборов Ai, которые перемещают "Голиаф" строго в кольцевую зону "R".
Считается, что точка (xx,yy) находится в кольцевой зоне "R", если расстояние между (xx,yy) и (mx,my) больше R1 меньше R2
(расстояние вычисляется по формуле \( \sqrt{(xx-m_x)^2+(yy-m_y)^2}\) )
- Среди отобранных наборов выбрать "лучший", то есть тот, для которого расстояние до центра кольцевой зоны "R" наименьшее
Так как Давид поступил в "КБ-1580" с "помощью DeepSeek", то он просит Вас выполнить его задание
Входные данные:
1 строка: вещественные значение x, y, m
x, m
y, R
1, R
2 и натуральное число K (К < 10000, остальные по модулю не более 10
9, R
1 < R
2)
следующие K строк - наборы чисел в формате: n a
n a
n-1 ... a
1
(вначале кол-во чисел в наборе, затем сами числа, все числа набора целые, по модулю не более 100, n <2000)
Выходные данные:
w, v, r - три числа в одной строке через пробел
w - количество наборов, "финальная точка" которых лежит в кольцевой зоне "R". Гарантируется, что w > 0
v - номер "лучшего" набора ("финальная точка" ближе всех к центру зоны "R"). Если таких несколько, то наименьший номер из "лучших"
r - расстояние до центра зоны "лучшего" набора. Указать только целую часть (как целое число).
Пример
| Входные данные |
Выходные данные |
Пояснение |
1 -1 1 -6 4 6 5
3 4 4 1
3 3 2 3
2 3 1
2 3 4
3 1 0 0 |
2 4 5 |
Начальная точка (1,-1)
Зона "R" - кольцевая зона с центром в (1,-6), внутренним радиусом 4 и внешним радиусом 6
количество наборов равно 5
1 набор размера 3 со значениями 4 4 1, перемещает робота "Голиаф" в (-7, -17)
(квадрат расстояния до центра зоны 185)
2 набор размера 3 со значениями 3 2 3, перемещает робота "Голиаф" в (-3, -13)
(квадрат расстояния до центра зоны 65)
3 набор размера 2 со значениями 3 1, перемещает робота "Голиаф" в (1, -7)
(квадрат расстояния до центра зоны 1)
4 набор размера 2 со значениями 3 4, перемещает робота "Голиаф" в (4, -10)
(квадрат расстояния до центра зоны 25)
5 набор размера 3 со значениями 1 0 0, перемещает робота "Голиаф" в (-2, -2)
(квадрат расстояния до центра зоны 25)
Внутри зоны будет только 2 набора (4 и 5), набор 3 перемещает во внутреннюю часть кольца, а наборы 1 и 2 перемещают во внешнюю часть
Лучшим набором будет 4, поскольку его номер меньше.
Расстояние будет \(\sqrt{25}\), целая часть 5
|