시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 142 | 30 | 18 | 27.692% |
평면에 여러 개의 점이 주어져 있다. 이 점들에는 각각 번호가 1번부터 차례대로 붙어 있다. 그리고 같은 번호의 점들은 각각 2개씩의 쌍으로 준비되어 있다. 따라서 전체 점의 수는 반드시 짝수 개이다. 우리는 같은 번호를 가진 두 개의 점을 대각선의 꼭짓점으로 하는 직사각형으로 연결하고자 한다. 이 직사각형을 연결사각형이라고 부른다. 문제는 다음의 세가지 조건을 만족하면서 서로 겹치지 않는 여러 개의 연결사각형을 찾아내는 것이다.
위의 조건을 만족시키면서 가장 높은 점수를 얻도록 하는 프로그램을 작성하시오.
첫 줄에는 쌍의 수가 주어진다. 그 다음 줄부터는 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