이사하자!

시간 제한1초메모리 제한1024 MB

요약
임의의 방향으로 놓인 정사각형 N개가 주어질 때, 각 정사각형이 다음 정사각형을 내부에 포함하는 최장 사슬의 길이를 구한다.
난이도

보통10점 중 7점

유형
기하, 동적 계획법, 정렬
정답자
아직 제출이 없습니다

문제

춘배와 상자1

춘배는 2차원 평면 위에 고정된 정사각형의 둘레와 그 내부를 포함하는 영역인 상자에 살고 있다. 춘배는 지금 살고 있는 상자가 너무 좁다고 생각해 더 넓은 상자로 이주할 계획을 세웠다. 춘배는 보미가 가지고 있는 상자 여러 개 중에서 가장 마음에 드는 상자를 구매해 입주하게 되었다.

춘배는 여러 상자를 둘러보던 중 몇 개의 상자는 다른 상자를 완전히 포함하고 있어 큰 상자를 구매하면 큰 상자가 포함하는 다른 상자들도 같이 구매할 수 있다는 사실을 깨달았다!

춘배를 도와 한 번에 최대한 많은 상자를 구매할 방법을 알려주자.

입력

첫 번째 줄에 상자의 개수를 나타내는 정수 NN이 주어진다. (1≤N≤75)(1 \le N \le 75)

두 번째 줄부터 NN개의 줄에 걸쳐 상자의 네 꼭짓점의 좌표 (x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)(x\_1, y\_1), (x\_2, y\_2), (x\_3, y\_3), (x\_4, y\_4)가 순서대로 공백으로 구분되어 주어진다. (0≤x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4≤2,000)(0 \le x\_1, y\_1, x\_2, y\_2, x\_3, y\_3, x\_4, y\_4 \le 2\\,000)

주어지는 좌표는 모두 정수이며 상자는 항상 정사각형이다.

출력

춘배가 한 번에 구매할 수 있는 상자의 최대 개수를 출력한다.

힌트

보미는 왜 상자를 x축과 y축에 맞춰 정렬하지 않고 흩어놨을까? 좌표축에 평행하지 않은 입력이 들어올 수 있음을 유념하여 풀어야 한다.

예제2

  1. 예제 1

    입력
    5
    0 0 0 10 10 10 10 0
    1 1 1 3 3 1 3 3
    4 4 8 8 4 8 8 4
    11 1 16 6 16 1 11 6
    12 2 13 2 13 3 12 3
    
    예상 출력
    3
    
  2. 예제 2

    입력
    2
    1 1 1 2 2 2 2 1
    1 2 2 2 2 1 1 1
    
    예상 출력
    2