Матч 431, Стрельба из лазера (LaserShooting)

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

 

Лазерная пушка расположена в точке (0, 0) на плоскости. Целями являются вертикальные отрезки с координатами концов (x[i], y1[i]) – (x[i], y2[i]). Выбирается произвольный угол от -π / 2 до π / 2 и производится выстрел. Выстрел под углом -π / 2 производится вертикально вниз, 0 – горизонтально вправо, π / 2 – вертикально вверх. Выстрелом является бесконечный луч, исходящий из начала координат. Выстрел попадает в цель, если луч и отрезок цели имеют общую точку.

Вычислить ожидаемое количество целей, которое может быть поражено одним выстрелом. Попадание в цель не меняет движение луча.

 

Класс: LaserShooting

Метод: double numberOfHits(vector<int> x, vector<int> y1,

                           vector<int> y2)

Ограничения: x, y1 и y2 содержат одинаковое количество элементов, все элементы массива x разные, 1 £ x[i] £ 1000, -1000 £ y1[i], y2[i] £ 1000.

 

Вход. Массивы x, y1 и y2, описывающие положения целей.

 

Выход. Ожидаемое количество целей, которое может быть поражено одним выстрелом.

 

Пример входа

x

y1

y2

{1}

{-1}

{1}

{3,4,7,1}

{1,2,3,4}

{4,3,2,1}

{134,298,151,942}

{-753,-76,19,568}

{440,689,-39,672}

 

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

0.5

0.4623163952488826

1.444210260641501

 

 

РЕШЕНИЕ

вероятность

 

Математическое ожидание суммы случайных величин равно сумме математических ожиданий этих величин. Поэтому достаточно вычислить для каждой цели ожидаемое количество выстрелов для ее поражения и просуммировать полученные значения.

Обозначим через a1 и a2 углы, при которых поражаются концы i - ой цели. Поскольку значения элементов массива x положительны, то a1 = arctg(y1[i] / x[i]), a2 = arctg(y2[i] / x[i]). i - ая цель поражается, если угол выстрела лежит между min(a1, a2) и max(a1, a2). Вероятность попадания в i - ую цель равна вероятности того, что точка, выбранная из отрезка [-π / 2, π / 2], попадет в отрезок [min(a1, a2) и max(a1, a2)]. Она равна (max(a1, a2) – min(a1, a2)) / π.

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

#include <cmath>

#define PI acos(-1.0)

using namespace std;

 

class LaserShooting

{

public:

  double numberOfHits(vector<int> x, vector<int> y1, vector<int> y2)

  {

    double a1, a2, res = 0.0;

    for(int i = 0; i < x.size(); i++)

    {

      a1 = atan(1.0 * y1[i] / x[i]);

      a2 = atan(1.0 * y2[i] / x[i]);

      res += fabs(a1 - a2) / PI;

    }

    return res;

  }

};