N-orthotope Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
1000 ms | 256 MiB | 63 | 35 | 33 | 94.29% |
축에 평행한 $N$-orthotope란 다음에 속하는 어떤 $N$ 차원 점들의 집합이다.
$[s_{1}, e_{1}] \times [s_{2}, e_{2}] \times ... \times [s_{N}, e_{N}]$ ($s_{i} < e_{i}$)
(즉, $N$차원 점 $(x_{1}, x_{2}, ..., x_{N})$의 각 $x_{i}$ 가 $s_{i} \le x_{i} \le e_{i}$ 인 점들의 집합이다.)
$N = 0$인 경우는 특별히 0차원의 점이라고 정의하자.
$N = 1$인 경우는 1차원에서 어느 선분을 의미한다.
$N = 2$인 경우는 2차원에서 축에 평행한 어느 직사각형 형태의 영역이 된다.
$N = 3$인 경우는 3차원에서 축에 평행한 어느 직육면체 형태의 영역이 된다.
...
조금 더 일반화하면,
$[s_{1}, e_{1}] \times [s_{2}, e_{2}] \times ... \times [s_{K}, e_{K}]$ ($s_{i} \le e_{i}$)
를 만족하는 점들은 $s_{i} < e_{i}$를 만족하는 $i$의 개수가 $N$개라면 축에 평행한 $N$-orthotope가 된다. 앞으로 '평행한'을 생략할 것이지만 앞으로 등장하는 orthotope도 평행한 orthotope라고 생각하면 된다.
어떤 $N$에 대해 두 개의 $N$-orthotope가 주어져 있다고 하자. 이때 두 영역에 동시에 속하는 점들이 있다면, 이 점들은 축에 $M$-orthotope가 된다. 이때 $M$이 무엇인지 구하는 프로그램을 작성하라. 예를 들어 $2$-orthotope의 경우 아래의 네 가지 경우가 있을 수 있다.
A는 두 2-orthotope의 공통된 영역이 똑같이 2-orthotope가 되는 경우이다.
B는 두 2-orthotope의 공통된 영역이 1-orthotope(선분)가 되는 경우이다.
C는 두 2-orthotope의 공통된 영역이 0-orthotope(점)가 되는 경우이다.
D는 두 2-orthotope의 공통된 영역이 없는 경우이다. 이 경우 -1을 출력하면 된다.
입력 형식
첫 번째 줄에 자연수 $N$이 주어진다.
두 번째 줄에는 첫 번째 영역의 $s_{1}, e_{1}, s_{2}, e_{2}, ?, s_{N}, e_{N}$이 공백으로 구분되어 주어진다.
세 번째 줄에는 두 번째 영역의 $s_{1}, e_{1}, s_{2}, e_{2}, ?, s_{N}, e_{N}$이 공백으로 구분되어 주어진다.
이 수들은 모두 절댓값이 $11$ 이하이며, 각 $s_{i}$, $e_{i}$는 $s_{i} < e_{i}$를 만족한다.
쉬운 문제에서는 $1 \le N \le 2$인 입력이 주어진다.
어려운 문제에서는 $1 \le N \le 11$인 입력이 주어진다.
출력 형식
첫 번째 줄에 두 영역의 공통된 영역이 $M$-orthotope이면 $M$을 출력한다. 단 공통된 영역이 없는 경우 -1을 출력한다.
예제 1
입력
2
0 5 0 5
2 9 2 9
출력
2
예제 2
입력
2
0 5 0 5
5 10 5 10
출력
0