시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 10 4 26.667%

문제

평면에 여러 개의 점이 주어져 있다. 이 점들에는 각각 번호가 1번부터 차례대로 붙어 있다. 그리고 같은 번호의 점들은 각각 2개씩의 쌍으로 준비되어 있다. 따라서 전체 점의 수는 반드시 짝수 개이다. 우리는 같은 번호를 가진 두 개의 점을 대각선의 꼭지점으로 하는 직사각형으로 연결하고자 한다. 이 직사각형을 연결사각형이라고 부른다. 문제는 다음의 세가지 조건을 만족하면서 서로 겹치지 않는 여러 개의 연결사각형을 찾아내는 것이다.

  1. 연결사각형은 반드시 같은 번호의 점을 대각선 꼭지점으로 해야 한다.
    • 만일 서로 다른 번호의 점을 직사각형으로 연결하면 안된다.
  2. 각 연결사각형은 반드시 서로 떨어져 있어야 한다.
    • 그림-1과 같은 경우는 허용되지 않는다.
    • 그림-2와 같이 두 연결사각형의 변이나 꼭지점이 서로 붙어있는 경우나, 
    • 그림-3과 같이 어떤 직사각형이 다른 직사각형 안에 포함되는 경우도 
    • 허용되지 않는다. 
  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

힌트

출처

Olympiad > 한국정보올림피아드 > KOI 1998 > 중등부 2번

  • 빠진 조건을 찾은 사람: doju