[2018 SCPC 본선]
기판
2차원 평면인 기판에 \(N\)개의 양극점과 \(N\)개의 음극점이 있다.
기판에 배선을 해야 하는데, 배선은 하나의 양극점과 하나의 음극점을 잇는 선분이어야 한다.
이러한 배선을 최대한 많은 양극점과 음극점의 쌍에 대해서 만들고 싶다.
단, 아래의 두 조건이 만족되어야 한다.
- 양극점이나 음극점 하나에 연결된 배선은 최대 하나이다.
- 두 배선이 교차하면 안된다.
아래 그림은 \(N=6\)인 경우이며, 6개의 배선을 조건에 맞게 구성한 것을 보여준다.
보기 편하도록 양극점은 별로, 음극점은 삼각형으로 표시하였다.
이 문제의 목표는 가능한 많은 배선을 만드는 것이다.
아래 테스트 케이스 그룹에 점수를 정하는 방법이 나와 있다.
- 제한시간: 전체 테스트 케이스는 26개 이하이며, 전체 수행 시간은 5초 이내. (Java 9초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있습니다.
단, 사용한 출력 함수에 따라서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 될 수 있습니다.
부분 점수를 제대로 받기 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 각 테스트 케이스를 처리한 후에 “fflush(stdout);”을 한번씩 호출하십시오.
Java에서는 "BufferedWriter"를 사용하시오.
(*** 이 문제에서는 “setbuf()”나 “System.out.printIn”을 사용하지 마시오. ***)
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. \((1 ≤ T ≤26 )\)
각 테스트 케이스의 첫 줄에는 양극점과 음극점의 개수 \(N\)이 주어진다.\((1≤N≤50,000)\)
다음 \(N\)개의 줄에는 양극점의 좌표가 \(x\)와 \(y\) 좌표로 주어진다.
그 다음 \(N\)개의 줄에는 음극점의 좌표가 \(x\)와 \(y\) 좌표로 주어진다.
양극점과 음극점은 주어진 순서대로 1번부터 \(N\)번까지 번호가 붙어 있다. 좌표 값은 1 이상 1,000,000,000 이하의 정수이다.
주어진 \(2N\)개의 점들 중 2개 이상이 동일한 위치이거나, 3개 이상이 한 직선 위에 있는 경우는 없다. 점들은 랜덤한 좌표에 주어진다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 256점)
주어지는 테스트 케이스 데이터들의 그룹과 채점 방식은 아래와 같다.
ㆍ 그룹 1 (64점) : 이 그룹의 테스트 케이스에서는 \(1≤N≤7\)이다.
ㆍ 그룹 2 (192점) : 이 그룹의 테스트 케이스에서는 추가적인 제약 사항이 없다.
- 그룹 1채점 방식: 모든 테스트 케이스를 맞추어야 점수를 받을 수 있다. 각 테스트 케이스에 대해서 \(N\)개의 배선을 만들어야 한다.
- 그룹 2채점 방식: 한 그룹에 속한 테스트 케이스들에는 동일한 점수가 배정된다. 각 테스트케이스에 할당된 만점을 \(P\)라 두자.
만약, 여러분의 프로그램이 찾은 배선의 개수 \(L\)에 대해서 \(L≥{7N \over 10}\)이면 \(P\) 점을 받고, 그렇지 않으면 \({5P \over 2N}(L-{3N \over 10})\)점을 받을 것이다.
만약 \({5P \over 2N}(L-{3N \over 10})\)이 음수이면 0점으로 처리된다. 각 테스트 케이스에 대해 구한 점수의 합이 그룹 2에 대한 점수가 된다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다.
이때 \(C\)는 테스트 케이스의 번호이다.
그 다음 줄에 여러분의 프로그램이 찾은 배선의 개수 \(L\) 을 출력한다.
다음 \(L\) 개의 줄에 배선으로 이어진 양극점과 음극점의 번호 쌍을 한 줄에 하나씩 출력한다.
(양극점과 음극점은 주어진 순서대로 1번부터 \(N\)번까지 번호가 붙어 있다.)
입출력예
| 입력 |
|---|
| 2 2 1 1 2 2 4 2 3 1 3 1 1 1 3 2 2 4 2 4 1 3 4 |
| 출력 |
|---|
| Case #1 2 1 2 2 1 Case #2 2 1 1 3 3 |