Koza [A]
Limit pamięci: 256 MB
Kum Bajtazar wziął swój dziesięciokilogramowy młot i na nieograniczonym
pastwisku wbił w ziemię palików. Przez kolejnych dni, każdego ranka
kum wyprowadza na pastwisko kozę i przywiązuje ją do losowo wybranego palika
postronkiem o długości . W ciągu dnia koza zjada całą trawę będącą w jej
zasięgu. Ku zmartwieniu kozy, trawa nie odrasta i co gorsza, koza może być
wiele razy przywiązywana do tego samego palika.
Jaka jest wartość oczekiwana pola powierzchni pastwiska, na której po
dniach nie będzie trawy?
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite
, oraz (), oznaczające odpowiednio liczbę
palików, liczbę dni, przez które trwał wypas kozy, oraz długość postronka. Każdy
z kolejnych wierszy zawiera współrzędne jednego palika w postaci pary liczb
całkowitych , (). Każdy palik
jest wbity w innym punkcie.
Wyjście
W jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę rzeczywistą
określającą wartość oczekiwaną pola powierzchni tej części pastwiska, z której
koza zje trawę w ciągu dni. Wynik zostanie zaakceptowany, jeśli będzie się
różnił od poprawnej odpowiedzi nie więcej niż o . Po kropce dziesiętnej
nie powinno znajdować się więcej niż 20 cyfr.
Przykład
Dla danych wejściowych:
2 2 1
0 0
1 0
poprawną odpowiedzią jest:
4.098204131080311
Wyjaśnienie do przykładu:
Jeśli w oba dni koza będzie przywiązana do tego samego palika, to
pole powierzchni zjedzonej trawy wyniesie , jeśli zaś do różnych,
to .
Zatem odpowiedzią jest .
Autor zadania: Tomasz Idziaszek.