연결 사각형
시간 제한1초메모리 제한128 MB
인덱스를 가중치로 갖는 N개의 축 정렬 직사각형 중 서로 겹치거나 닿지 않는 부분집합을 골라 가중치 합을 최대화합니다.
문제
평면 위에 여러 점이 주어집니다. 점에는 1부터 N까지 번호가 붙어 있고, 각 번호마다 정확히 두 점이 있습니다. 같은 번호의 두 점을 서로 마주 보는 꼭짓점으로 하는 축에 평행한 직사각형을 만들 수 있으며, 이를 연결 사각형이라고 합니다.
여러 번호를 선택해 연결 사각형을 만들 때, 선택한 직사각형들은 서로 떨어져 있어야 합니다. 두 직사각형이 겹치는 경우는 물론, 변이나 꼭짓점이 닿는 경우도 허용되지 않습니다. 한 직사각형이 다른 직사각형 안에 포함되는 경우도 선택할 수 없습니다.
번호 i의 연결 사각형을 선택하면 i점을 얻습니다. 조건을 만족하도록 연결 사각형들을 골라 얻을 수 있는 총점을 최대화하는 프로그램을 작성하세요.
입력
첫 줄에 쌍의 수 N이 주어집니다. 다음 N줄에는 1번부터 N번까지 순서대로 각 번호에 해당하는 두 점의 좌표 x1 y1 x2 y2가 주어집니다.
N은 50 이하입니다. 모든 좌표는 1000 이하의 양의 정수입니다. 같은 번호의 두 점은 같은 수직선이나 같은 수평선 위에 있지 않습니다.
출력
첫 줄에 선택한 쌍의 수를 출력합니다. 둘째 줄에는 선택한 연결 사각형의 번호를 오름차순으로 공백으로 구분해 출력합니다.