Вероятность через эксперимент
Математики часто решали задачи, проводя симуляции или эксперименты. Например, значение пи () можно приблизительно определить, случайным образом размещая точки в квадрате, который вписан в круг. Если квадрат имеет размеры 250×250, его площадь составляет 62500, а площадь вписанного круга равна пи*125²=15625пи. Поскольку точки размещаются случайным образом, можно предположить, что количество точек внутри круга и общее количество точек в квадрате пропорциональны их соответствующим площадям. Таким образом, значение пи можно приблизительно определить, подсчитав, сколько точек находится внутри круга (Рисунок 1). Значение пи можно также определить с помощью более сложного эксперимента, например, эксперимента с иглой Буффона (Рисунок 2).
Рисунок 1: Приближение пи путем подсчета количества точек внутри круга
Оба упомянутых эксперимента для приближенного определения значения пи можно легко смоделировать, написав компьютерную программу. Было бы замечательно провести такой эксперимент много раз (например, 1 миллиард миллиардов) и получить почти идеальный результат, но из-за нехватки времени это невозможно в реальной жизни. В этой задаче вам нужно будет написать программу, которая поможет профессору Ву провести аналогичный эксперимент, но эта программа может быть не такой простой.
Рисунок 2: Эксперимент с иглой Буффона
Профессор Нил Ву пытается решить классическую задачу с помощью симуляции: если три точки случайным образом размещены на границе круга, какова вероятность того, что они будут вершинами острого треугольника? Конечно, эту задачу можно решить аналитически, и результат, который он получает, равен 0.25. Теперь он хочет проверить этот результат через эксперимент. Результат можно приблизительно найти, размещая три случайные точки на круге миллиарды раз и подсчитывая, сколько раз эти три точки образуют острый треугольник. Прелесть такого эксперимента (как упоминалось выше) заключается в том, что если мы увеличим количество испытаний, результат станет еще более точным. Но если доктор Ву хочет повторить этот процесс 1000 миллиардов раз, это займет 2 часа, а если он хочет повторить его миллиард миллиардов раз, это может занять более 200 лет. Доктор Ву обнаружил, что этот процесс можно ускорить, используя другой подход — генерировать n случайных точек на границе круга, и они образуют треугольники как вершины. Сколько из этих треугольников являются острыми? Если количество острых треугольников равно M и пусть N = , тогда желаемая вероятность равна . Таким образом, имея n точек на границе, вы должны помочь доктору Ву, написав очень эффективную программу для нахождения количества острых треугольников.
Рисунок 3: Пример круга с заданными точками на границе
Входные данные
Входной файл содержит около 40 тестовых случаев. Однако большинство случаев не являются экстремальными, поэтому размер входного файла составляет около 3 МБ. Описание каждого тестового случая приведено ниже.
Каждый случай начинается с двух положительных целых чисел n (0 < n ≤ 20000) и r (0 < r ≤ 500). Здесь n — это общее количество точек на границе круга, а r — радиус круга. Центр круга всегда находится в начале координат (0, 0). Каждая из следующих N строк обозначает расположение одной точки на границе круга. Каждая точка обозначается P, определенной числом с плавающей запятой θ (0.000 ≤ θ < 360.000). Это θ — это угол (выраженный в градусах), который точка P образует в центре круга с положительным направлением оси x. Таким образом, декартовы координаты P равны (r*cos(θ), r*sin(θ)). Значение θ всегда будет иметь ровно три знака после запятой. Ни две точки не будут находиться в одном месте.
Строка, содержащая два нуля, завершает ввод. Эта строка не должна обрабатываться.
Выходные данные
Каждый тестовый случай производит одну строку вывода. Эта строка содержит порядковый номер вывода, за которым следует целое число. Это целое число обозначает, сколько из треугольников, образованных этими n точками, на самом деле являются острыми треугольниками.
Примечание: 20000 точек, сгенерированных на границе круга, могут на самом деле создать 20000*19999*19998/6 1333 миллиардов треугольников. Таким образом, эксперимент для 1333 миллиардов можно провести за, скажем, 0.5 секунды. Тогда эксперименты с 1 миллиардом миллиардов треугольников можно провести примерно за 100 часов (в отличие от 200 лет, упомянутых ранее), просто повторяя этот эксперимент. Также, если мы разместим 1817120 точек на границе круга, создается около 1 миллиарда миллиардов треугольников, и количество острых треугольников среди этого большого числа треугольников можно вычислить за 5 минут.