Матч 431, Падающие точки (FallingPoints)

Дивизион 2, Уровень 2

Имеется несколько точек, характеризующиеся абсцисой и бесконечной оординатой. Последовательно, начиная с первой, точки падают на ось абсцисс. Каждая точка движется вниз до тех пор, пока либо она не станет находиться на расстоянии R от предыдущей точки, либо пока не достигнет оси y = 0. Каждая точка начинает движение только после того, как предыдущая завершит падение. Найти ординату каждой упавшей точки.

Класс: FallingPoints

Метод: vector<double> getHeights(vector<int> x, int r)

Ограничения: x содержит от 1 до 50 элементов, 0 £ x[i], r £ 1000.

Вход. Массив x, содержащий абсцисы точек, и целое значение r.

Выход. Массив, i - ый элемент которого содержит ординату i - ой упавшей точки.

Пример входа

x	r
{1, 100}	10
{0, 9}	10
{0, 9, 19}	10

Пример выхода

{0.0, 0.0}

{0.0, 4.358898943540674}

{0.0, 4.358898943540674, 4.358898943540674}

РЕШЕНИЕ

геометрия

Первая точка обязательно упадет на ось абсцисс, поэтому res[0] = 0, где res – возвращющийся вектор. Для нахождения ординаты i - ой точки следует решить уравнение

относительно res_i и выбрать больший корень. То есть

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

class FallingPoints

{

public:

vector<double> getHeights(vector<int> x, int r)

{

vector<double> res(x.size(),0);

int i;

for(i = 1; i < x.size(); i++)

if (abs(x[i] - x[i-1]) <= r)

res[i] = res[i-1] +

sqrt(1.0 * r * r - (x[i] - x[i-1]) * (x[i] - x[i-1]));

return res;

}

};