정사각형 만들기

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

요약

내부가 모두 유리로 덮여 있고 변이 기존 유리 경계선을 따르는 가장 작은 정사각형의 넓이를 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 이분 탐색, 구간
정답자: 아직 제출이 없습니다

문제

당신은 스테인드글라스 모자이크에서 모양이 불규칙한 조각 하나를 얻었습니다. 오랜 보관으로 많이 손상되었고 가장자리의 많은 부분이 빠져 있습니다. 기념으로 그중 작은 부분을 간직하고 싶습니다.

모자이크에서 완전한 정사각형 부분을 찾아 떼어 냅니다. 유리 판 사이에 이미 있는 선을 따라서만 조각을 떼어 낼 수 있으며, 유리를 자를 수는 없습니다.

그림 G.1: 첫 번째 입력 예의 시각화. 오른쪽 위 모서리에서 5 × 5cm 조각을 떼어 낼 수 있습니다.

유리는 다루기 번거로워서 필요 이상으로 가져가고 싶지 않습니다. 유리를 손상시키지 않고 한 조각으로 떼어 낼 수 있는 가장 작은 정사각형은 무엇입니까?

입력

첫 줄에 유리 조각의 개수를 나타내는 정수 $n$ ( $1 \le n \le 10^8$ )이 주어집니다. 이어지는 $n$ 개 줄에는 각각 정수 $x_0$ , $y_0$ , $x_1$ , $y_1$ ( $0 \le x, y \le 10^8$ )이 주어집니다. 이는 한 조각의 왼쪽 아래 모서리와 오른쪽 위 모서리의 좌표(cm 단위)입니다. 어떤 두 유리 조각도 서로 겹치지 않습니다.

출력

기존 선을 따라 떼어 낼 수 있는 가장 작은 정사각형의 넓이를 제곱센티미터 단위로 출력합니다. 어떤 정사각형도 떼어 낼 수 없다면 impossible을 출력합니다.

예제2

예제 1

입력

13
20 16 22 19
20 15 22 16
19 14 22 15
10 10 12 20
12 10 20 14
12 14 17 15
19 15 20 18
17 18 20 19
12 19 20 20
12 15 17 17
12 17 17 18
12 18 17 19
17 14 19 18

예상 출력

예제 2

입력

예상 출력

impossible