9319번 - 도청 장치 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 230 | 87 | 82 | 42.051% |
문제
이번 주에 알고스팟 회의가 암스테르담에서 열린다. 전국 대학생 프로그래밍 대회 동아리 연합(이하 전대프연) 회장 성진이는 알고스팟 회의를 도청하려고 한다. 성진이는 도청장치를 회의 장소 근처에 숨겨놓았다. 도청장치는 계속해서 녹음하며, 무선 전파를 이용해서 전송한다.
성진이는 전대프연 회원들에게 도청장치의 수신기를 나누어주었고, 여러 장소에 흩어 보냈다. 전파는 서로 간섭을 일으킨다. 따라서, 전혀 듣지 못하는 장소가 있을 수 있다. 수신기를 가진 한 회원의 위치가 주어졌을 때, 그 사람이 들을 수 있는 도청장치를 구하는 프로그램을 작성하시오.
어떤 장소에서 들을 수 있는 도청장치는 다음과 같은 식을 만족하는 \(i\)번째 도청장치이다.
\[r_i > 6(B+\sum_{j \ne i} {r_j})\]
- \(r_i = \frac{s_i} {\left| P_i - P_{listen} \right| ^2}\)는 \(i\)번째 도청장치의 신호 수신 세기이다.
- \(s_i\)는 \(i\)번째 도청장치가 보낸 신호의 세기이다.
- \(P_i\)는 \(i\)번째 도청장치의 위치이다.
- \(P_{listen}\)는 수신기를 들고있는 사람의 위치이다.
- \(\left| P_i - P_{j} \right|\) \(P_i\)와 \(P_j\) 사이의 유클리드 거리이다.
- \(B\)는 백그라운드 노이즈의 레벨이다.
입력
첫째 줄에 테스트 케이스의 수가 주어지며, 100을 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 도청장치의 수 \(n\) (0 ≤ \(n\) ≤ 100,000)이 주어진다. 둘째 줄에는 백그라운드 노이즈의 레벨 \(B\) (0 ≤ \(B\) ≤ 1,000,000)가 주어진다. 셋째 줄에는 수신기를 들고있는 사람의 위치 x좌표와 y좌표 \(x\)와 \(y\)가 주어진다. 다음 \(n\)개 줄에는 \(i\)번째 도청장치의 위치 \(x_i\), \(y_i\)와 신호의 세기 \(s_i\)가 주어진다. (0 ≤ \(s_i\) ≤ 1,000,000)
모든 좌표는 구간 [0, 10000]에 포함되며, 모든 도청장치의 위치 \(P_i\)와 수신기의 위치 \(P_{listen}\)는 다르다. 테스트 케이스는 소수점 오차가 정답에 영향을 주지 않게 설계되어져 있다.
출력
첫째 줄에 들을 수 있는 도청장치의 번호를 출력한다. 만약, 들을 수 있는 도청장치가 없다면 "NOISE"를 출력한다.
도청장치의 번호는 1부터 시작한다.
예제 입력 1
3 4 10 100 100 90 90 20000 110 90 50 90 110 1000 110 110 50 4 100 100 100 90 90 20000 110 90 50 90 110 1000 110 110 50 2 0 0 10 0 0 1000 0 8 1
예제 출력 1
1 NOISE 1
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries B번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호