시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 591 | 219 | 167 | 35.381% |
상혁이는 부농이 되기 위해 낯선 나라의 한 황무지에 정착했다. 상혁이는 황무지에 농작물 N개를 심었다. 이 농작물은 물만 주면 매일매일 수확할 수 있는 신기한 작물이다.
농작물 N개를 심은 뒤에야 상혁이는 황무지를 농토로 개간하는 걸 계획하기 시작했다. 황무지를 2차원 평면으로 생각하자. 상혁이는 (0, 0)을 중심으로 반경 r 내의 모든 황무지를 개간하기로 했다. 이 개간된 농토를 관리하는데 매일 A × r2 달러가 소비된다.
각 농작물 i는 (xi, yi)에 심겨 있고 wi만큼의 가치를 가지고 있다. 황무지에 심어진 농작물에서는 아무것도 수확할 수 없다. 농토의 경계에 놓인 농작물도 수확할 수 있다. 농토에 심어진 농작물의 수확량은 아래와 같이 계산된다.
농작물로부터 농토 경계까지의 최단 거리를 ci 라고 하면, 농작물마다 매일 wi × ci 달러
위의 예시는 농작물들과 농토를 2차원 좌표평면 상에 나타낸 그림이다. 초록색 원(r = 3)은 농토의 경계를 의미한다. 농작물 밑에 나온 수들은 농작물의 가치이다. 이 때 농토 바깥에 있는 농작물들은 황무지에 있으므로 수확되지 않는다.
가치 30인 농작물에서 농토 경계까지의 최단 거리는 위의 빨간 선분으로 표시되어 있고 아래에 그 거리의 값이 소수점 아래 2번째 자리까지 나타나 있다. 이런 구성에서 A = 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 이내인 경우에만 정답이다.
4 10 1 1 30 -2 -1 50 -1 -2 20 2 -2 70
325.558936
본문의 예시에 해당하는 입력이다.
5 10 1 3 50 -5 -2 80 3 1 40 2 -3 60 8 8 100
659.3779
2 20 1 1 10 2 2 20
0
University > 서강대학교 > 2019 Sogang Programming Contest > Champion F번