페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6353
스페셜 저지

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

문제

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

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

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


입력

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

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


출력

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


출처

The 2024 ICPC Latin America Championship I번

로그인해야 코드를 작성할 수 있어요.