Təcrübə vasitəsilə ehtimal
Riyaziyyatçılar tez-tez problemləri simulyasiya və ya təcrübələr vasitəsilə həll edirlər. Məsələn, pi () dəyərini kvadratın içində təsvir olunan dairədə təsadüfi nöqtələr yerləşdirərək təxmin etmək mümkündür. Əgər kvadratın ölçüsü 250×250 olarsa, onun sahəsi 62500, təsvir olunan dairənin sahəsi isə pi*125²=15625pi olur. Təsadüfi yerləşdirilən nöqtələrin dairənin içindəki sayı və kvadratda yerləşdirilən ümumi nöqtələrin sayı onların sahələrinə nisbətlidir. Beləliklə, pi dəyəri dairənin içindəki nöqtələrin sayını sayaraq təxmin edilə bilər (Şəkil 1). Pi dəyəri hətta Buffon iynəsi təcrübəsi kimi daha mürəkkəb bir təcrübə ilə də müəyyən edilə bilər (Şəkil 2).
Şəkil 1: Dairənin içindəki nöqtələrin sayılması ilə pi dəyərinin təxmini
Yuxarıda qeyd olunan iki təcrübə pi dəyərini təxmin etmək üçün asanlıqla bir kompüter proqramı ilə simulyasiya edilə bilər. Bu cür təcrübəni çox sayda (məsələn, 1 milyard milyard) həyata keçirmək və demək olar ki, mükəmməl nəticə əldə etmək yaxşı olardı, lakin vaxt məhdudiyyəti səbəbindən bunu real həyatda edə bilmirik. Bu məsələdə, siz Professor Vuya oxşar bir təcrübə aparmağa kömək edəcək bir proqram yazmalısınız, lakin bu proqram o qədər də sadə olmaya bilər.
Şəkil 2: Buffon iynəsi təcrübəsi
Professor Neal Wu simulyasiya vasitəsilə klassik bir problemi həll etməyə çalışır: Əgər üç nöqtə dairənin sərhədində təsadüfi yerləşdirilərsə, onların kəskin bucaqlı üçbucaq əmələ gətirmə ehtimalı nədir? Bu problem analitik olaraq həll edilə bilər və nəticə 0.25-dir. İndi o, bu nəticəni təcrübə ilə təsdiqləmək istəyir. Nəticə dairədə təsadüfi üç nöqtə yerləşdirərək və bu üç nöqtənin kəskin bucaqlı üçbucaq əmələ gətirdiyi halları sayaraq təxmin edilə bilər. Belə bir təcrübənin gözəlliyi (yuxarıda qeyd olunduğu kimi) odur ki, sınaqların sayını artırsaq, nəticə daha dəqiq olacaq. Lakin Dr. Wu bu prosesi 1000 milyard dəfə təkrarlamaq istəsə, bu 2 saat vaxt aparacaq və əgər bunu milyard milyard dəfə təkrarlamaq istəsə, bu 200 ildən çox vaxt ala bilər. Dr. Wu bu prosesi fərqli bir yanaşma ilə sürətləndirə biləcəyini kəşf etdi – dairənin sərhədində n təsadüfi nöqtə yaradın və onlar üçbucaqlar əmələ gətirir. Bu üçbucaqlardan neçəsi kəskin bucaqlıdır? Əgər kəskin bucaqlı üçbucaqların sayı M və N = , onda istənilən ehtimal . Beləliklə, sərhəddəki n nöqtə verildikdə, Dr. Wuya kəskin bucaqlı üçbucaqların sayını tapmaq üçün çox səmərəli bir proqram yazmaqda kömək etməlisiniz.
Şəkil 3: Sərhəddə verilmiş nöqtələrlə dairə nümunəsi
Giriş verilənləri
Giriş faylı təxminən 40 test halı ehtiva edir. Lakin halların əksəriyyəti ekstremal deyil, buna görə giriş faylının ölçüsü təxminən 3 MB-dır. Hər bir test halının təsviri aşağıda verilmişdir.
Hər bir hal iki müsbət tam ədəd n (0 < n ≤ 20000) və r (0 < r ≤ 500) ilə başlayır. Burada, n dairənin sərhədindəki nöqtələrin ümumi sayıdır və r dairənin radiusudur. Dairənin mərkəzi həmişə orijindədir (0, 0). Növbəti N sətirin hər biri dairənin sərhədindəki bir nöqtənin yerini göstərir. Hər bir nöqtə P, ondalık nöqtədən sonra üç rəqəm olan bir θ (0.000 ≤ θ < 360.000) ilə təmsil olunur. Bu θ əslində nöqtənin dairənin mərkəzində x-oxunun müsbət istiqaməti ilə yaratdığı bucaqdır. Beləliklə, P-nin Kartezyen koordinatı (r*cos(θ), r*sin(θ)) olur. θ dəyəri həmişə ondalık nöqtədən sonra dəqiq üç rəqəm olacaq. Heç bir iki nöqtə eyni yerdə olmayacaq.
İki sıfırdan ibarət bir sətir girişi bitirir. Bu sətir işlənməməlidir.
Çıxış verilənləri
Hər bir test halı bir çıxış sətiri yaradır. Bu sətir çıxışın seriyasını və ardınca bir tam ədəd ehtiva edir. Bu tam ədəd bu n nöqtələri ilə əmələ gələn üçbucaqların neçəsinin əslində kəskin bucaqlı üçbucaq olduğunu göstərir.
Qeyd: Dairənin sərhədində yaradılan 20000 nöqtə əslində 20000*19999*19998/6 1333 milyard üçbucaq yarada bilər. Beləliklə, 1333 milyard təcrübə, məsələn, 0.5 saniyədə edilə bilər. Sonra 1 milyard milyard üçbucaqla təcrübələr təxminən 100 saatda edilə bilər (Əvvəllər qeyd olunan 200 illə müqayisədə) sadəcə bu təcrübəni təkrarlamaqla. Həmçinin, əgər dairənin sərhədində 1817120 nöqtə yerləşdirsək, təxminən 1 milyard milyard üçbucaq yaradılır və bu böyük sayda üçbucaqlar içindəki kəskin bucaqlı üçbucaqların sayı 5 dəqiqə ərzində hesablana bilər.