시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB59121916735.381%

문제

상혁이는 부농이 되기 위해 낯선 나라의 한 황무지에 정착했다. 상혁이는 황무지에 농작물 N개를 심었다. 이 농작물은 물만 주면 매일매일 수확할 수 있는 신기한 작물이다.

농작물 N개를 심은 뒤에야 상혁이는 황무지를 농토로 개간하는 걸 계획하기 시작했다. 황무지를 2차원 평면으로 생각하자. 상혁이는 (0, 0)을 중심으로 반경 r 내의 모든 황무지를 개간하기로 했다. 이 개간된 농토를 관리하는데 매일 A × r2 달러가 소비된다.

각 농작물 i는 (xi, yi)에 심겨 있고 wi만큼의 가치를 가지고 있다. 황무지에 심어진 농작물에서는 아무것도 수확할 수 없다. 농토의 경계에 놓인 농작물도 수확할 수 있다. 농토에 심어진 농작물의 수확량은 아래와 같이 계산된다.

농작물로부터 농토 경계까지의 최단 거리를 ci 라고 하면, 농작물마다 매일 wi × ci 달러

위의 예시는 농작물들과 농토를 2차원 좌표평면 상에 나타낸 그림이다. 초록색 원(= 3)은 농토의 경계를 의미한다. 농작물 밑에 나온 수들은 농작물의 가치이다. 이 때 농토 바깥에 있는 농작물들은 황무지에 있으므로 수확되지 않는다.

가치 30인 농작물에서 농토 경계까지의 최단 거리는 위의 빨간 선분으로 표시되어 있고 아래에 그 거리의 값이 소수점 아래 2번째 자리까지 나타나 있다. 이런 구성에서 = 10 이라 할 때, 관리비용은 10 × 3 × 3 = 90, 농작물로부터 얻는 이득은 총 약 113.058936이다. 따라서 이 때 상혁이가 얻는 이득은 약 23.058936달러이다. (최대 이득은 아니다)

A와 농작물들의 좌표, 가치들이 주어졌을 때, 농토 관리 비용과 농작물 총 수확량을 고려할 때 상혁이가 최대로 이득을 보기 위한 r을 결정해 주자.

입력

첫 번째 줄에 정수 N과 정수 A가 주어진다. (1 ≤ N ≤ 105, 1 ≤ A ≤ 103)

두 번째 줄부터 N + 1번째 줄까지, 각 줄마다 정수 xi, yi, wi 가 주어진다. (−103 ≤ xi, yi ≤ 103, 1 ≤ wi ≤ 200)

출력

상혁이가 황무지를 개간하여 얻을 수 있는 최대의 이득(달러)를 출력한다. 만약 아예 개간하지 않는 것이 최대 이득을 준다면 0을 출력한다.

상대/절대 오차가 10−6 이내인 경우에만 정답이다.

예제 입력 1

4 10
1 1 30
-2 -1 50
-1 -2 20
2 -2 70

예제 출력 1

325.558936

본문의 예시에 해당하는 입력이다.

예제 입력 2

5 10
1 3 50
-5 -2 80
3 1 40
2 -3 60
8 8 100

예제 출력 2

659.3779

예제 입력 3

2 20
1 1 10
2 2 20

예제 출력 3

0

출처

University > 서강대학교 > 2019 Sogang Programming Contest > Champion F번