19291번 - Donut-shaped Enclosure 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 24 | 11 | 9 | 50.000% |
문제
2차원 평면에서 보통 사용되는 거리 체계는 유클리드(Euclid) 거리다. 유클리드 거리에서 두 점 $(x_1, y_1)$과 $(x_2, y_2)$사이의 거리는 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$로 나타낸다.
이 문제에서는 유클리드 거리 대신 체비쇼프(Chebyshev) 거리를 다룬다. 체비쇼프 거리에서 $(x_1, y_1)$과 $(x_2, y_2)$사이의 거리는 $\max{(|x_1 - x_2|, |y_1 - y_2|)}$로 나타낸다.
어떤 거리 체계에 대하여 반지름이 $r$인 원은 특정한 점 $(x_c, y_c)$와의 거리가 $r$인 점 $(x,y)$의 집합이다. 원의 형태는 어떤 거리 체계를 쓰느냐 에 따라 다른데, (그림 1)에서 보이듯 유클리드 거리에서는 우리가 보통 아는 원형이고, 체비쇼프 거리에서는 한 변의 길이가 $2r$인 정사각형이 원이 된다.
그림 1 : 유클리드 거리와 체비쇼프 거리에서의 원
또한, 어떤 거리 체계에 대하여 안쪽 반지름이 $l$이고, 바깥쪽 반지름이 $r$인 도넛은 특정한 점 $(x_c, y_c)$와의 거리가 $l$이상 $r$이하인 점 $(x,y)$들의 집합이다.
(그림 2)에서 왼쪽은 유클리드 거리에서의 도넛이고, 오른쪽은 체비쇼프 거리에서의 도넛이다. 회색 영역이 도넛에 포함된 영역이다.
그림 2 : 유클리드 거리와 체비쇼프 거리에서의 도넛
범수는 $N$개의 점 $P_1$, $P_2$, $\cdots$, $P_N$과 체비쇼프 거리에서의 안쪽 반지름이 $L$이고 바깥쪽 반지름이 $R$인 도넛을 가지고 놀고 있다. $P_i$는 $(x_i, y_i)$에 위치하며, 도넛중심의 위치는 중심의 좌표를 격자점에 두는 것만 지키면, 범수가 마음껏 바꿀 수 있다. 만약 $P_i$가 도넛 영역에 들어가 있다면, 범수는 강제적으로 $S_i$점을 얻게 되고, 도넛 영역에 들어가 있지 않다면 아무 점수도 얻지 않는다. 이 때, 범수가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 세 정수 $N$, $L$, $R$($1 ≤ N ≤ 10^5$, $1 ≤ L ≤ R ≤ 10^9$)이 공백 하나로 구분되어 주어진다.
다음 $N$개의 줄의 $i$번째 줄에는 $x_i$, $y_i$, $S_i$($-10^9 ≤ x_i, y_i ≤ 10^9$, $-10^4 ≤ S_i ≤ 10^4$)가 공백 하나로 구분되어 주어진다. 같은 위치에 여러 점이 있을 수 있다.
출력
첫 번째 줄에 범수가 얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력 1
4 1 1 0 1 1 0 -1 1 1 0 -100 -1 0 -100
예제 출력 1
2
예제 입력 2
4 1 2 0 1 1 0 -1 1 1 0 -100 -1 0 -100
예제 출력 2
1
힌트
첫 번째 예제는 도넛의 중심을 $(1,0)$이나 $(-1,0)$에 두면 된다.
두 번째 예제는 도넛이 너무 커졌기 때문에, $-100$을 피해서 $1$하나를 포함 시키는 것이 최적이다.
출처
Camp > Petrozavodsk Programming Camp > Winter 2018 > Day 5: Grand Prix of Korea A번
Contest > kriiicon > 제5회 kriiicon DE번
Contest > Open Cup > 2017/2018 Season > Stage 10: Grand Prix of Korea A번
- 문제를 만든 사람: august14
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호