Page not loading? Try clicking here.
Placeholder

#6353
Special judge

Insects, Mathematics, Accuracy, and Efficiency 0.5s 1024MB

Problems

Bog의 삶에는 세 가지 열정이 있습니다: 곤충, 수학, 정확성, 그리고 효율성입니다. 그의 마지막 열정은 처음 두 가지를 합치는 것이었기에, Bog는 미분 풀사슴이라는 귀여운 녹색 친구를 입양하기로 결정했습니다.

Dydx라고 명명한 이 작은 녹색 친구를 기쁘게 하기 위해, Bog는 그에게 작은 굴을 만들었습니다. 그는 반지름이 R인 원 안의 어떤 작물이든 물을 줄 수 있는 스프링클러를 샀고, 이 원 안에 N개의 작물을 심었습니다.

Dydx는 새로운 집을 정말 좋아했습니다! 그러나 Bog는 미분 풀사슴이 모든 작물을 감싸는 가장 작은 볼록 다각형으로 정의된 영역 안에만 머물 것이라는 것을 깨달았습니다. 이제 그는 작물을 더 퍼뜨리지 않은 것을 후회합니다. 다행히도, Bog는 아직 심지 않은 마지막 작물을 찾았습니다. Bog는 당신의 도움을 원해서 Dydx가 스프링클러의 범위 내에 마지막 작물을 심어 Dydx가 거주할 수 있는 영역을 최대화하고 싶어합니다.


Input

첫 번째 줄에는 두 정수 NR이 주어집니다. (1 ≤ N, R ≤ 10^4) 이는 각각 심어진 작물의 수와 스프링클러로 정의된 원의 반지름을 나타냅니다. 작물은 이차원 평면에서 점으로 표현되며, (0, 0)은 스프링클러의 좌표를 나타냅니다.

다음 N개의 줄 중 i번째 줄은 농작물이 좌표 (X, Y)에 심어졌음을 나타내는 두 정수 XY를 포함합니다. (X, Y)에서 (0, 0)까지의 유클리드 거리는 최대 R입니다. 모든 작물의 위치는 서로 다릅니다.


Output

스프링클러의 범위 내에 추가로 심은 작물로 Dydx가 거주할 수 있는 최대 영역의 넓이를 한 줄에 출력하세요. 출력은 최대 10^{-9}의 절대 또는 상대 오차를 가질 수 있습니다. 추가된 작물은 정수 좌표를 가질 필요가 없습니다.


Source

The 2024 ICPC Latin America Championship I번

You must sign in to write code.