Василий поступил программистом на работу в "КБ-1580", занимающимся разработкой робота "Варяг".
Василий получил первое задание. Описание задания:
- Необходимо переместить "Варяг" из "начальной точки" в "финальную точку" одним из K представленных способов
так, чтобы "финальная точка" находилась в орбитальной зоне "М2" (задается двумя фокусами и суммой расстояний до них)
- "начальная точка" и "финальная точка" - точки плоскости, заданные с помощью значений абсциссы и ординаты
(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) - координаты "начальной точки"
- (m1x,m1y), (m2x,m2y) - координаты фокусов орбитальной зоны "М2"
- RM - допустимая сумма расстояний до фокусов орбитальной зоны "М2" (зона "М2" - эллипс)
- \(A_1,\dots,A_K\) - наборы чисел, определяющие перемещение "Авроры"
Василий
должен определить:
- количество наборов Ai, которые перемещают "Варяг" строго в орбитальную зону "М2".
Считается, что точка (xx,yy) находится в орбитальной зоны "М2", если сумма расстояний между (xx,yy) , (m1x,m1y) и (xx,yy) , (m2x,m2y) меньше RM
(сумма расстояний вычисляется по формуле \( \sqrt{(xx-m1_x)^2+(yy-m1_y)^2} +\sqrt{(xx-m2_x)^2+(yy-m2_y)^2}\) )
- Среди отобранных наборов выбрать "лучший", то есть тот, для которого сумма расстояний до фокусов орбитальной зоны "М2" наименьшее
Так как Василий поступил в "КБ-1580" с "помощью DeepSeek", то он просит Вас выполнить его задание
Входные данные:
1 строка: вещественные значение x, y, m1
x, m1
y, m2
x, m2
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 - расстояние до центра зоны "лучшего" набора. Указать только целую часть (как целое число).
Пример
| Входные данные |
Выходные данные |
Пояснение |
0 -1 -3 -4 -2 -2 5 5
2 2 0
2 1 0
2 2 3
2 4 2
2 3 4 |
|
Начальная точка (0,-1)
Зона "M2" - задается фокусами (-3, -4), (-2, -2) и суммой расстояний 5
количество наборов равно 5
1 набор размера 2 со значениями 2 0, перемещает "Варяг" в (-2,0)
(сумма расстояний до фокусов примерно 4.12 + 2 = 6.12 )
2 набор размера 2 со значениями 1 0, перемещает "Варяг" в (-1,0)
(сумма расстояний до фокусов примерно 4.47 + 2.24 = 6.71 )
3 набор размера 2 со значениями 2 3, перемещает "Варяг" в (-2,-3)
(сумма расстояний до фокусов примерно 1.41 + 1 = 2.41 )
4 набор размера 2 со значениями 4 2, перемещает "Варяг" в (-4,-2)
(сумма расстояний до фокусов примерно 2.24 + 2 = 4.24 )
5 набор размера 2 со значениями 3 4, перемещает "Варяг" в (-3,-4)
(сумма расстояний до фокусов примерно 0 + 2.24 =2.24 )
Внутри зоны будет только 3 набора (3, 4 и 5),
Лучшим набором будет 5
Расстояние будет \(0 + \sqrt{2}\), а целая часть 2
|
| |
|
|