Ймовірність через експеримент
Математики часто вирішують задачі, проводячи симуляції або експерименти. Наприклад, значення пі () можна приблизно визначити, випадково розміщуючи точки в квадраті, в який вписане коло. Якщо квадрат має розмір 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 хвилин.