Ймовірність через експеримент#4091
Математики часто вирішують задачі, проводячи симуляції або експерименти. Наприклад, значення пі можна приблизно визначити, випадково розміщуючи точки в квадраті, в який вписане коло. Якщо квадрат має розмір 250 \times 250, його площа дорівнює , а площа вписаного кола становить \pi \cdot 125^2 = 15625\pi. Оскільки точки розміщуються випадково, можна припустити, що кількість точок всередині кола і загальна кількість точок у квадраті пропорційна їх площам. Таким чином, значення пі можна приблизно визначити, підрахувавши, скільки точок знаходиться всередині кола (Рисунок 1). Значення пі можна також визначити за допомогою більш складного експерименту, такого як експеримент з голкою Буффона (Рисунок 2).
Рисунок 1: Приблизне визначення пі шляхом підрахунку кількості точок всередині кола
Два експерименти, згадані вище, для приблизного визначення значення пі можуть бути змодельовані шляхом написання комп'ютерної програми. Було б добре провести такий експеримент багато разів (скажімо, мільярд мільярдів) для отримання майже ідеального результату, але через брак часу це неможливо в реальному житті. У цій задачі вам потрібно написати програму, яка допоможе професору Ву провести подібний експеримент, але ця програма може бути не такою простою.
Рисунок 2: Експеримент з голкою Буффона
Професор Ніл Ву намагається вирішити класичну задачу за допомогою симуляції: якщо три точки випадково розміщені на межі кола, яка ймовірність, що вони утворять гострокутний трикутник? Цю задачу можна вирішити аналітично, і результат, який він отримує, становить . Тепер він хоче перевірити цей результат через експеримент. Результат можна знайти приблизно, розміщуючи три випадкові точки на колі мільярди разів і підраховуючи, скільки разів ці три точки утворюють гострокутний трикутник. Краса такого експерименту полягає в тому, що зі збільшенням кількості спроб результат стає точнішим. Але якщо доктор Ву хоче повторити цей процес мільярдів разів, це займе години, а якщо мільярд мільярдів разів, це може зайняти понад років. Доктор Ву виявив, що цей процес можна прискорити, використовуючи інший підхід — генерувати випадкових точок на межі кола, які утворюють трикутники як вершини. Скільки з цих трикутників є гострокутними? Якщо кількість гострокутних трикутників дорівнює , і нехай N = {n \choose 3}, тоді бажана ймовірність є \frac{M}{N}. Отже, маючи точок на межі, ви повинні допомогти доктору Ву, написавши дуже ефективну програму для знаходження кількості гострокутних трикутників.
Рисунок 3: Приклад кола з заданими точками на межі
Вхідний файл містить близько тестових випадків. Більшість випадків не є екстремальними, тому розмір вхідного файлу становить близько МБ. Опис кожного тестового випадку наведено нижче.
Кожен випадок починається з двох додатних цілих чисел (0 < n \le 20000) та (0 < r \le 500). Тут — це загальна кількість точок на межі кола, а — радіус кола. Центр кола завжди знаходиться в початку координат . Кожен з наступних рядків позначає розташування однієї точки на межі кола. Кожна точка позначена числом з плаваючою комою (0.000 \le \theta < 360.000). Це фактично є кутом (вираженим у градусах), який точка утворює в центрі кола з позитивним напрямком осі . Отже, декартова координата — це (r \cdot \cos(\theta), r \cdot \sin(\theta)). Значення завжди матиме рівно три цифри після десяткової точки. Жодні дві точки не будуть у тому ж місці.
Рядок, що містить два нулі, завершує вхід. Цей рядок не слід обробляти.
Кожен тестовий випадок створює один рядок виходу. Цей рядок містить серійний номер виходу, за яким слідує ціле число. Це ціле число позначає, скільки з трикутників, утворених цими точками, насправді є гострокутними.
Примітка: точок, згенерованих на межі кола, можуть фактично створити 20000 \cdot 19999 \cdot 19998 / 6 \approx 1333 мільярдів трикутників. Отже, експеримент для мільярдів може бути виконаний, скажімо, за секунди. Тоді експерименти з мільярдом мільярдів трикутників можуть бути виконані приблизно за годин (на відміну від років, згаданих раніше), просто повторюючи цей експеримент. Також, якщо ми розмістимо точок на межі кола, буде створено близько мільярда мільярдів трикутників, і кількість гострокутних трикутників серед цієї великої кількості трикутників може бути обчислена за хвилин.
Приклад 1