Афанасий поступил программистом на работу в "КБ-1580", занимающимся разработкой робота "Аврора".
Афанасий получил первое задание. Описание задания:
- Необходимо переместить "Аврору" из "начальной точки" в "финальную точку" одним из K пердставленных способов
так, чтобы "финальная точка" находилась в целевой зоне "М" (задается центром и радиусом)
- "начальная точка" и "финальная точка" - точки плоскости, заданные с помощью значений абсциссы и ординаты
(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) - координаты центра целевой зоны "М"
- RM - радиус целевой зоны "М" (зона "М" - круг радиуса RM)
- \(A_1,\dots,A_K\) - наборы чисел, определяющие перемещение "Авроры"
Афанасий
должен определить:
- количество наборов Ai, которые перемещают "Аврору" строго в целевую зону "М".
Считается, что точка (xx,yy) находится в целевой зоне "М", если расстояние между (xx,yy) и (mx,my) меньше RM
(расстояние вычисляется по формуле \( \sqrt{(xx-m_x)^2+(yy-m_y)^2}\) )
- Среди отобранных наборов выбрать "лучший", то есть тот, для которого расстояние до центра целевой зоны "М" наименьшее
Так как Афанасий поступил в "КБ-1580" с "помощью DeepSeek", то он просит Вас выполнить его задание
Входные данные:
1 строка: вещественные значение x, y, m
x, m
y, R
M и натуральное число K (К < 10000, остальные по модулю не более 10
9)
следующие K строк - наборы чисел в формате: n a
n a
n-1 ... a
1
(вначале кол-во чисел в наборе, затем сами числа, все числа набора целые, по модулю не более 100, n <2000)
Выходные данные:
w, v, r - три числа в одной строке через пробел
w - количество наборов, "финальная точка" которых лежит в зоне "М". Гарантируется, что w > 0
v - номер "лучшего" набора ("финальная точка" ближе всех к центру зоны "М"). Если таких несколько, то наименьший номер из "лучших"
r - расстояние до центра зоны "лучшего" набора. Указать только целую часть (как целое число).
Пример
| Входные данные |
Выходные данные |
Пояснение |
1 -1 1 -9 4 5
2 3 2
2 2 1
2 3 0
3 2 3 3
3 1 3 2 |
3 1 1 |
Начальная точка (1,-1)
Зона "M" - круг радиуса 4 с центром в (1,-9)
количество наборов равно 5
1 набор размера 2 со значениями 3 2, перемещает "Аврору" в (2,-8)
(квадрат расстояния до центра зоны 2)
2 набор размера 2 со значениями 2 1, перемещает "Аврору" в (1,-5)
(квадрат расстояния до центра зоны 16)
3 набор размера 2 со значениями 3 0 перемещает "Аврору" в (0,-6)
(квадрат расстояния до центра зоны 10)
4 набор размера 3 со значениями 2 3 3 перемещает "Аврору" в (-1,-13)
(квадрат расстояния до центра зоны 16)
5 набор размера 3 со значениями 1 3 2 перемещает "Аврору" в (0,-10)
(квадрат расстояния до центра зоны 2)
Внутри зоны будет только 3 набора (1, 3 и 5), наборы 2 и 4 будут на строго на границе и поэтому не учитываются
Лучшим набором будет 1, поскольку его номер меньше.
Расстояние будет \(\sqrt{2}\), а целая часть 1
|
| |
|
|