19552번 - 데이터 제작 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 88 | 18 | 17 | 26.154% |
문제
“정휘야, 데이터 만들어야지”
정휘는 원래 UCPC 2020 Call for Tasks에 점과 선분이 등장하는 재미있는 기하 문제를 제출하려고 했지만, 데이터를 너무 만들기 귀찮은 나머지 출제를 포기했다.
UCPC 2020에 문제를 꼭 출제하고 싶어 고민하고 있던 정휘는 아주 좋은 아이디어를 냈다. 바로 대회 참가자들에게 데이터를 만들게 하는 것이다! 원래는 정휘가 해야 할 일이었지만, 이제는 여러분이 좌표 평면상에 점 $N$개와 선분 $M$개를 적절히 배치해서 $K$개의 영역이 있는 데이터를 만들어야 한다.
영역은 평면 상의 빈 공간이며, 선분으로 모든 면이 둘러 쌓여 있어야 한다. 영역은 다른 영역으로 둘러 쌓여질 수도 있다. 좌표 범위가 너무 넓으면 계산하기 너무 힘들기 때문에, 79brue의 팬인 정휘는 모든 점의 좌표 범위를 $79$ 이하의 자연수로 제한하기로 했다!
여러분은 아래 조건을 모두 만족시키는 데이터를 만들어야 한다.
- 각 점의 $x$, $y$좌표는 $1$ 이상 $79$ 이하의 자연수가 되어야 한다.
- 모든 점의 위치는 서로 달라야 한다.
- 같은 두 점을 잇는 선분이 여러 개 존재하면 안 된다.
- 선분은 서로 다른 두 점을 이어야 한다.
- 서로 다른 두 선분은 끝점을 제외한 곳에서 교차하면 안 된다.
- 선분의 양 끝점을 제외한 점은 선분 위에 있으면 안 된다.
아래에서 (a)는 점 $3$개, 선분 $3$개로 $1$개의 영역을 만든 그림이고, (b)는 점 $4$개, 선분 $6$개로 $3$개의 영역을 만든 그림이다. (c)는 곡선이 존재하기 때문에, (d)는 교차하는 선분들이 존재하기 때문에 올바르지 않은 출력이다.
입력
첫 번째 줄에 배치해야 할 점의 개수, 선분의 개수와 만들어야 하는 영역의 개수를 나타내는 세 자연수 $N,M,K$가 주어진다. ($3 \leq N \leq 3\ 000$, $0 \leq M$, $0 \leq K$)
$N$개의 점과 $M$개의 서로 교차하지 않는 선분으로 $K$개의 다각형을 만들 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄부터 $N$번째 줄까지 $i$번째 줄에 $i$번째 점의 좌표를 출력한다. $N+1$번째 줄부터 $N+M$번째 줄까지 각 선분이 몇 번째 점을 연결하는지 출력한다.
예제 입력 1
4 6 3
예제 출력 1
1 1 3 1 2 2 2 3 1 2 1 3 1 4 2 3 2 4 3 4
예제 입력 2
6 5 1
예제 출력 2
1 1 1 2 2 1 3 1 3 2 4 1 1 2 1 3 2 3 4 5 5 6
노트
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호