2017번 - 울타리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 67 | 26 | 8 | 40.000% |
문제
농부 장길산은 자신의 밭을 감싸는 울타리를 관리하고 있다. 밭은 가로 세로 N미터인 정사각형 평지이다. (2 ≤ N ≤ 500000) 밭 경계의 한쪽 끝 좌표는 (0, 0)이며, 맞은편 끝 좌표는 (N, N)이다. 또한 경계는 x, y 축에 평행하다.
울타리를 나타내는 말뚝은 일단 밭의 네 모서리에 박혀 있고, 그 사이 네 변 구간에도 1미터 간격으로 박혀 있다. 따라서 말뚝은 총 4N개가 있다. 이 문제에서 말뚝은 땅 위로 솟아 있는 홀쭉한 선분이며 반지름, 즉 굵기가 없다고 가정한다. 길산은 밭 안 어느 위치에 서서 사방을 돌아볼 때, 거기서 밭의 끝 경계에 있는 말뚝을 몇 개까지 볼 수 있나 알고 싶어 한다.
그의 밭 안에는 R (1 ≤ R ≤ 30000)개의 커다란 바위가 있어서 그의 시야를 일부 가린다. 바위는 밑면과 윗면이 같은 볼록다각형으로 구성된 기둥이며, 높이가 충분히 높기 때문에 길산은 바위 너머로 있는 말뚝을 볼 수 없다. 바위들은 영역이 서로 겹치지 않으며, 꼭짓점이나 선분이 접하지도 않는다. 한 바위가 다른 바위 안이나 위에 있지도 않다.
길산이 가진 밭(울타리)의 크기, 길산이 밭 안에 있는 위치, 그리고 각 바위들에 대한 정보가 들어왔을 때, 그가 그 위치에서 고개만 돌려서 볼 수 있는 울타리 말뚝의 총 개수를 계산하는 프로그램을 작성하시오. 바위를 구성하는 임의의 한 정점과 농부와 일직선을 이루는 말뚝은 농부에게 보이지 않는다.
입력
첫 줄에는 N과 R의 값이 순서대로 들어있다. 다음 줄에는 장길산의 x, y 위치가 순서대로 들어있다. 그리고 다음 줄에는 R개의 바위에 대한 정보가 순서대로 들어온다.
바위에 대한 정보는 다각형을 기술하는 것과 같으므로, 가장 먼저 이 바위의 꼭짓점 개수를 나타내는 p가 있다. (3 ≤ p ≤ 20) 그리고 다음 p 줄에는 다각형을 구성하는 x y 좌표가 순서대로 들어온다. 꼭짓점의 좌표들은 모두 서로 값이 다르며 반시계 방향이다.
아래 예제의 (70, 40), (75, 40), (80, 40)처럼, 정점 좌표가 일직선 상에 있는 경우도 있을 수 있다.
출력
길산이 그 위치에서 볼수 있는 말뚝의 개수를 한 줄에다 출력하면 된다. 아래의 예제를 살펴보면, 농부는 (60, 50) 위치에 있는데 (70, 40) 위치의 바위 꼭짓점 때문에 (100, 10)부터. 또 (70, 60) 위치의 바위 꼭짓점 때문에 (100, 90)까지, 경계에 있는 81개의 말뚝이보이지 않게 된다. 따라서 정답은 400에서 81을 뺀 319이다.
예제 입력 1
100 1 60 50 5 70 40 75 40 80 40 80 50 70 60
예제 출력 1
319
힌트
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호