12801번 - 중계 신호 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 82 | 27 | 22 | 33.333% |
문제
어떤 섬에 사는 사람들이 있다. 이 사람들은 보통 어업을 생업으로 삼기 때문에 이 섬에 사는 사람들은 중 N개의 가구는 낚싯배를 가지고 있다. 사람들이 한창 일을 하러 나가는 오후에는 N개의 배가 모두 섬을 떠나 바다 위에 떠 있는데, 각 배들은 좌표 평면 위의 한 점으로 나타낼 수 있다. 또, 사람들이 살고 있는 섬은 M개의 점으로 이루어진 볼록 다각형으로 볼 수 있다. (우연히도, 모든 배들과 섬을 이루는 꼭짓점들은 격자점 위에 놓여 있다고 한다.) 다음 그림은 섬과 배의 배치의 예시이다.
(중앙의 주황색 볼록 다각형이 섬, 번호가 매겨진 파란 점들이 낚싯배다.)
각각의 배에는 라디오 통신 기기가 달려 있는데, 두 배 사이에 장애물이 없다면 이 통신 기기를 통해 두 배가 연락을 주고받을 수 있다. 정확히는, 어떤 두 배를 잇는 선분이 섬의 내부와 교차하지 않는다면 두 배는 연락을 주고받을 수 있다. (두 배를 잇는 선분이 볼록 다각형의 꼭짓점이나 변에만 닿는 것은 상관없다.)
어떤 배 A가 위험한 상황에 빠졌다고 하면, 그 배는 주위의 신호가 닿는 모든 배들에게 구조 신호를 전달한다. 그 후, 구조 신호를 수신한 모든 배들은 다시 신호가 닿는 모든 배들에게 A가 위험한 상황에 빠졌다는 중계 신호를 전달한다. 중계 신호를 수신한 배들이 다시 신호를 전달하지는 않는다.
당신은 섬을 이루는 M개의 점과 1~N의 번호가 붙은 N개의 배의 위치를 알고 있고, 1번 배가 위험한 상황에 빠졌다고 할 때 1번 배에게서 신호를 전달받는 배의 수를 구해야 한다. 이때, 신호를 전달받는 배라는 것은 1번 배가 처음에 발신한 구조 신호와 구조 신호를 수신한 배들이 발신한 중계 신호 중 하나라도 전달받은 배를 뜻한다. (1번 배는 신호를 전달받은 배로 치지 않는다.)
입력
첫 번째 줄에는 배의 수 N (1 ≤ N ≤ 100 000)이 주어진다.
이후의 N개 줄에는 배의 위치에 대한 정보가 주어진다. i번째 줄에는 i번 배의 x좌표와 y좌표가 공백을 사이에 두고 순서대로 주어진다.
다음 줄에는 섬을 이루는 꼭짓점의 수 M (3 ≤ M ≤ 100 000)이 주어진다.
이후의 M개 줄에는 각 꼭짓점의 좌표에 대한 정보가 주어진다. i번째 줄에는 섬의 i번째 꼭짓점의 x좌표와 y좌표가 공백을 사이에 두고 순서대로 주어진다.
주어지는 섬은 볼록 다각형이며, 섬을 이루는 점들은 반시계 방향으로 주어진다.
섬을 이루는 볼록 다각형의 인접한 두 변은 기울기가 같지 않음이 보장된다.
모든 배와 섬의 꼭짓점의 x좌표와 y좌표는 -109 이상, 109 이하이다.
모든 배들의 좌표가 다르고, 어느 배도 섬의 내부나 변 위에 존재하지 않는다.
출력
1번 배가 위험한 상황에 빠졌을 때, 1번 배에게서 구조 신호나 중계 신호를 전달받을 수 있는 배의 수를 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | 1 ≤ N ≤ 300, 3 ≤ M ≤ 300 |
| 2 | 19 | 1 ≤ N ≤ 3000, 3 ≤ M ≤ 3 000 |
| 3 | 20 | 1 ≤ N ≤ 100 000, 3 ≤ M ≤ 300 |
| 4 | 43 | 1 ≤ N ≤ 100 000, 3 ≤ M ≤ 100 000 |
예제 입력 1
9 9 6 8 5 10 8 8 8 -2 3 -1 5 9 1 0 1 -1 2 7 1 1 5 1 8 3 7 5 4 6 0 5 -1 3
예제 출력 1
6
예제 입력 2
4 -1 0 -3 -20 6 10 5 10 4 3 0 3 1 0 10 0 -10
예제 출력 2
2
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2016 > Croatian Olympiad in Informatics 2016 3번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호