3657번 - 총격전 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 36 | 8 | 7 | 50.000% |
문제
선영: "상근이가 총을 먼저 쐈어요!"
상덕: "아니에요. 희원이가 있는 쪽에서 총소리가 먼저 났어요!"
논쟁은 얼마 전에 있었던 큰 총격전에 대한 재판내내 계속 되었다. 다행히도 총격전에 참가한 모든 사람은 죽지 않았다. 하지만, 총이 발사된 순서는 모두가 동의하지 않았다. 모든 사람은 최대 한 발을 발사했다. 하지만, 모든 일이 너무나 빠르게 일어났다. 총이 발사된 순서를 알아내야 유죄와 무죄를 판결할 수 있기 때문에, 순서를 알아내는 것은 매우 중요하다.
갑자기 경찰관 현우가 논쟁에 끼어들었다.
현우: "난 총격전이 일어난 그 시점의 위성 사진을 가지고 있다. 너희들이 어디에 있는 지를 정확하게 알 수 있지. 상덕이는 상근이보다 희원이에게 매우 가깝게 있었고, 선영이는 상근이보다 희원이에게 조금 가깝게 있었군. 소리는 1초에 340m를 움직이지. 상덕이는 상근이가 총을 먼저 쐈다고 하더라도, 희원이의 총소리를 먼저 들었을 거야. 그런데, 선영이는 희원이에게 조금 가깝게 있었는데도 상근이의 총소리를 먼저 들었네? 상근이가 제일 처음으로 총을 발사한 사람이네!"
위와 같은 상황이 주어졌을 때, 총을 발사한 순서를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다.
테스트 케이스의 첫째 줄에는 총격전에 연루된 사람의 수 n (2 ≤ n ≤ 100)과 진술의 수 m (1 ≤ m ≤ 1000) 이 주어진다.
다음 n개 줄에는 사람의 이름 S와 그 사람의 위치 x와 y가 주어진다. 이름은 길이가 최대 20이며, 알파벳 소문자와 대문자로만 이루어져 있다. 좌표는 원점으로부터 떨어진 거리이며 단위는 미터이다.
다음 m개 줄에는 각 사람의 진술 "S1 heard S2 firing before S3"가 주어진다. S1, S2, S3은 사람의 이름이며, S2 ≠ S3이다.
만약, 어떤 사람이 S2, S3로 언급된 적이 없으면, 그 사람은 총을 쏘지 않았다고 가정한다. 두 사람이 같은 장소에 있는 경우는 없다.
테스트 케이스는 정답에 영향을 주지 않기 위해 거리의 오차가 10-7보다 작게 만들어져 있다.
출력
각 테스트 케이스 마다 총을 쏜 순서를 출력한다. 만약, 가능한 순서가 여러 가지라면 "UNKNOWN"을 출력하고, 가능한 순서가 없는 경우에는 "IMPOSSIBLE"을 출력한다.
예제 입력 1
3 4 2 BillyTheKid 0 0 Andy 10 0 John 19 0 Larry 20 0 Andy heard BillyTheKid firing before John Larry heard John firing before BillyTheKid 2 2 Andy 0 0 Beate 0 1 Andy heard Beate firing before Andy Beate heard Andy firing before Beate 3 1 Andy 0 0 Beate 0 1 Charles 1 3 Beate heard Andy firing before Charles
예제 출력 1
BillyTheKid John IMPOSSIBLE UNKNOWN
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 G번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호