정사각형

시간 제한2초메모리 제한128 MB

요약

최대 50개의 축에 평행한 사각형이 그려졌을 때, 겹치거나 이어진 선분들로 만들어지는 모든 정사각형의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 기하, 누적 합, 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

세준이는 생일 선물로 받은 연필로 하루 종일 직사각형을 그렸다.

그림을 그린 종이는 x-y 좌표평면으로 볼 수 있다. 모든 직사각형의 변은 좌표축과 평행하며, 이미 그린 직사각형의 변과 새로 그린 직사각형의 변이 겹치거나 이어질 수 있다. 이렇게 그려진 선분들을 이용하면 처음에 직접 그린 직사각형이 아니더라도 새로운 직사각형이나 정사각형의 둘레가 만들어질 수 있다.

아래 그림처럼 직사각형 3개를 그리면 만들 수 있는 정사각형은 모두 14개이다.

세준이가 그린 직사각형들의 정보가 주어졌을 때, 그려진 선분만을 변으로 사용해서 만들 수 있는 정사각형의 개수를 구하라.

입력

첫째 줄에 직사각형의 개수 N이 주어진다. N은 50 이하인 자연수이다.

다음 N개의 줄에는 세준이가 그린 직사각형이 한 줄에 하나씩 주어진다. 각 줄은 X1 Y1 X2 Y2 형식이며, (X1, Y1)은 직사각형의 왼쪽 아래 꼭짓점, (X2, Y2)는 오른쪽 위 꼭짓점이다.

모든 좌표는 1,000,000,000 이하인 음이 아닌 정수이고, 항상 X1 < X2, Y1 < Y2를 만족한다.

출력

그려진 직사각형의 변들로 만들 수 있는 정사각형의 개수를 출력한다.

예제3

예제 1
입력
```
3
0 0 3 3
1 0 2 3
0 1 3 2
```
예상 출력
```
14
```
예제 2
입력
```
2
0 0 2 4
2 0 4 4
```
예상 출력
```
1
```
예제 3
입력
```
3
0 0 1 3
0 3 4 4
3 0 4 3
```
예상 출력
```
0
```