33805번 - Red and Blue 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 103 | 43 | 37 | 43.023% |
문제
좌표평면에 $N$개의 점이 주어진다. $i$번째 점의 좌표는 $(x_i, y_i)$이다. 모든 점들은 위치가 서로 다르며, 한 직선 위에 세 점이 놓이게 되는 경우는 없다.
당신의 목표는 점들의 쌍들 중 일부를 빨간색, 또는 파란색 선분으로 연결하여 다음 조건들을 모두 만족하도록 하는 것이다.
- 빨간색 선분만을 고려할 때, 모든 점들은 연결되어있다. 즉, 아무 서로다른 두 점을 잡아도 해당 두 점을 양 끝 점으로 가지는 빨간색 선분으로 이루어진 경로가 존재한다. 파란색 선분만을 고려할 때에도 성립한다.
- 임의의 두 선분이 두 선분의 끝점을 제외한 곳에서 교점을 가지지 않는다.
- 선분의 색상과 상관없이, 선분은 최대 $2N-2$개까지 존재한다.
조건을 모두 만족하도록 선분을 그릴 수 있는지 판별하고, 만약 가능하다면 답을 출력하라.
입력
첫 줄에 점의 수 $N$이 주어진다.
다음 $N$개의 줄 중 $i$번째 줄에는 두 정수 $x_i, y_i$가 공백을 사이에 두고 주어진다.
출력
만약 조건을 모두 만족하도록 점들을 연결하는 것이 불가능하다면, 첫 줄에 -1을 출력한다.
그렇지 않을 경우, 답을 출력한다. 첫 줄에는 답에 사용된 선분의 개수 $m$을 출력한다.
다음 $m$개의 줄 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$, 한 문자 $c_i$를 공백을 사이에 두고 출력한다. 이는 답에 사용된 $i$번째 선분이 $a_i$번째, $b_i$번째 점을 끝점으로 하는 선분임을 의미하며, $c_i$가 R일 경우 빨간색, B일 경우 파란색임을 의미한다.
제한
- $3 \le N \le 2\,000$
- 모든 $1 \le i \le N$에 대하여 $|x_i|, |y_i| \le 1\,000\,000\,000$
- 모든 $1 \le i<j \le N$에 대하여 $(x_i, y_i) \ne (x_j, y_j)$
- 주어진 $N$개의 점 중 세 점이 한 직선 위에 놓이게 되는 경우는 없다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $N \le 5$ |
| 2 | 31 | $N \le 100$ |
| 3 | 58 | 추가적인 제약 조건이 없다. |
예제 입력 1
4 0 0 5 5 5 10 10 0
예제 출력 1
6 1 3 R 1 4 R 1 2 B 4 3 B 2 3 B 2 4 R
예제 입력 2
5 0 0 3 7 5 0 5 2 7 3
예제 출력 2
8 1 5 R 1 3 R 1 4 B 3 5 B 4 5 B 4 3 R 1 2 R 2 5 B
예제 입력 3
4 -1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000 1000000000
예제 출력 3
-1
출처
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest F번
- 문제를 만든 사람: flappybird
- 문제를 검수한 사람: ainta, gs22123, ibm2006, koosaga, leinad2, moonrabbit2, silverwolf, urd05
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호