정사각형 만들기

면접 대비

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

요약

각각 90도 회전할 수 있는 직사각형 세 개를 겹침이나 빈틈 없이 이어 붙여 정사각형 하나를 만들 수 있는지 판정한다.

난이도: 보통10점 중 5점
유형: 기하, 구현, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

직사각형 세 개가 주어진다. 세 직사각형을 서로 겹치지 않게 붙여서 정사각형 하나를 빈틈 없이 채울 수 있는지 판정한다. 각 직사각형은 90도 회전할 수 있고, 자르거나 남길 수는 없다. 세 직사각형의 넓이 합이 곧 정사각형의 넓이가 되어야 한다.

예를 들어 $8 \times 2$ , $1 \times 6$ , $7 \times 6$ 직사각형은 $8 \times 8$ 정사각형을 채운다. $8 \times 2$ 조각이 위쪽 한 줄을 통째로 덮고, 그 아래 남은 $8 \times 6$ 영역을 $1 \times 6$ 조각과 $7 \times 6$ 조각이 나란히 채운다.

세 직사각형이 8x8 정사각형을 채운 그림

입력

입력은 세 줄로 이루어진다.

첫째 줄에 첫 번째 직사각형의 너비 $w_1$ 과 높이 $h_1$ 이 공백으로 구분되어 주어진다. ( $1 \le w_1, h_1 \le 100$ )

둘째 줄에 두 번째 직사각형의 너비 $w_2$ 와 높이 $h_2$ 가 주어진다. ( $1 \le w_2, h_2 \le 100$ )

셋째 줄에 세 번째 직사각형의 너비 $w_3$ 과 높이 $h_3$ 이 주어진다. ( $1 \le w_3, h_3 \le 100$ )

출력

세 직사각형으로 정사각형을 만들 수 있으면 $1$ , 만들 수 없으면 $0$ 을 한 줄에 출력한다.

예제6

예제 1
입력
```
8 2
1 6
7 6
```
예상 출력
```
1
```
예제 2
입력
```
2 8
6 1
6 7
```
예상 출력
```
1
```
예제 3
입력
```
1 1
1 1
1 1
```
예상 출력
```
0
```
예제 4
입력
```
1 1
1 1
2 1
```
예상 출력
```
1
```
예제 5
입력
```
3 1
3 1
3 1
```
예상 출력
```
1
```
예제 6
입력
```
4 2
4 1
4 1
```
예상 출력
```
1
```