레이팅 미적용평면에 여러 개의 점이 주어져 있다. 이 점들에는 각각 번호가 1번부터 차례대로 붙어 있다. 그리고 같은 번호의 점들은 각각 2개씩의 쌍으로 준비되어 있다. 따라서 전체 점의 수는 반드시 짝수 개이다. 우리는 같은 번호를 가진 두 개의 점을 대각선의 꼭짓점으로 하는 직사각형으로 연결하고자 한다. 이 직사각형을 연결사각형이라고 부른다. 문제는 다음의 세가지 조건을 만족하면서 서로 겹치지 않는 여러 개의 연결사각형을 찾아내는 것이다.
-
연결사각형은 반드시 같은 번호의 점을 대각선 꼭짓점으로 해야 한다.
-
만일 서로 다른 번호의 점을 직사각형으로 연결하면 안 된다.
-
각 연결사각형은 반드시 서로 떨어져 있어야 한다.
-
그림-1과 같은 경우는 허용되지 않는다.
-
그림-2와 같이 두 연결사각형의 변이나 꼭짓점이 서로 붙어있는 경우나,
-
그림-3과 같이 어떤 직사각형이 다른 직사각형 안에 포함되는 경우도
-
허용되지 않는다.
-
연결사각형을 만들었을 때에 얻는 점수는 그 쌍에 부여된 번호와 같다.
-
따라서 그림-4와 같이 연결했을 경우에 얻는 점수는 1+4+5+\(6=16\)점이다.
위의 조건을 만족시키면서 가장 높은 점수를 얻도록 하는 프로그램을 작성하시오.
첫 줄에는 쌍의 수가 주어진다. 그 다음 줄부터는 1번부터 순서대로 두 점의 좌표가 나온다. 점들의 수는 50쌍(100개) 이하이다. 각 점의 좌표는 1000 이하의 양의 정수이다. 쌍을 이루는 두 점은 같은 수직선이나 같은 수평선 상에 있지 않다.
첫 줄에는 선택된 쌍의 수를 출력한다. 그 다음 줄에는 선택된 연결사각형의 번호를 오름차순으로 출력한다.
6
2 5 1 3
5 6 3 2
5 2 6 4
7 6 5 8
1 6 5 4
3 7 7 3
3
1 3 4
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 1998 > 2차 대회 > 중등부 2번