시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 38 | 19 | 14 | 56.000% |
21XX년, 당신이 사는 행성은 큰 위기를 맞았고 행성의 대표인 당신은 FTL (Faster Than Light) 엔진을 이용하여 최근에 발견된 "BOJ-1014" 행성으로 사람들을 이주시킬 계획을 세우고 있다.
당신이 사는 행성에는 N개의 나라가 있으며 M개의 우호적 관계가 있고 "BOJ-1014" 행성에는 L (L ≥ N) 개의 거주지역이 있다. 거주지역은 2차원 좌표평면에 나타내었을 때 i번 거주 지역은 Pi(Xi, Yi) (1 ≤ i ≤ L) 에 있다. 각 거주지역에는 오직 한 나라만 들어설 수 있다.
어떤 두 나라가 우호적 관계에 있으면 그 두 나라를 잇는 철도를 건설해야 한다. 철도는 두 나라를 잇는 선분이며 한 철도가 다른 철도와 교차하는 상황이 발생할 수 있다. 철도가 서로 교차하는 점이 있을 때 위험할 수 있고 건설 비용도 더 많이 들어가므로 가능한 교차하는 철도의 쌍을 최소화 하고자 한다.
당신의 행성의 나라와 우호적 관계 그리고 이주할 행성의 정보가 주어졌을 때 나라들을 잘 배치하여 교차하는 철도의 쌍의 개수를 가능한 적게 만드는 프로그램을 작성하자.
총 5개의 부분 문제로 구성되어 있으며 한 개의 부분문제는 한 개의 입력 데이터를 가진다. (밑의 힌트 부분을 참조)
입력 파일의 형식은 다음과 같다.
모든 입력 데이터는 다음 조건을 만족한다.
입력 파일에 대하여 출력 데이터를 제출하면 된다. 출력 데이터는 총 N줄로 구성되어 있고 k (1 ≤ k ≤ N) 번째 줄에는 k번 나라가 위치한 지역의 번호가 있어야 한다.
6 10 1 2 1 3 1 4 1 5 1 6 2 4 2 6 3 4 3 5 4 6 7 2 1 2 5 4 3 6 7 7 3 8 5 9 1
1 5 4 2 7 3
이 문제는 압축 파일의 01.txt로 채점을 합니다.
주의
나라를 배치하는 방법에 따라 한 점에서 2개 이상의 철도가 교차할 수 있다.
부분 문제
각 부분 문제에 대하여 N, M, L, S, T 값은 아래의 테이블을 참조하길 바란다. 여기서 S와 T는 점수 측정을 위한 값이다.
Subtask | N | M | L | S | T |
---|---|---|---|---|---|
1 | 30 | 50 | 60 | 25 | 100 |
2 | 125 | 124 | 300 | 0 | 75 |
3 | 200 | 2000 | 400 | 110000 | 250000 |
4 | 250 | 350 | 250 | 400 | 2000 |
5 | 300 | 1600 | 500 | 72000 | 150000 |
점수 측정
이 문제는 출력 데이터를 제출하여 점수를 받을 수 있으며 총 5개의 부분 문제가 있다. 각 부분 문제는 한 개의 데이터 파일로 구성되어 있으며 제출 시 아래의 조건에 따라 점수를 받을 수 있다.
예제 입력과 출력
예제의 입력에선 총 7개의 거주지역이 있으며 아래의 그림과 같다.
총 6개의 나라가 있으며 다음과 같이 배치하고자 한다.
그다음 우호관계에 따라 철도를 건설하면 아래의 그림과 같이 된다. 총 2개의 철도 쌍이 교차하는 것을 알 수 있다.
Contest > JOI Open Contest > JOI Open Contest 2014 4-1번