B - Intersection of Cuboids Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250

問題文

あなたは3Dゲームの当たり判定を実装しようとしています。

3 次元空間内の直方体であって、2(a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
(この定義により C(a,b,c,d,e,f) は一意に定まります)

2 つの直方体 C(a,b,c,d,e,f)C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。

制約

  • 0 \leq a < d \leq 1000
  • 0 \leq b < e \leq 1000
  • 0 \leq c < f \leq 1000
  • 0 \leq g < j \leq 1000
  • 0 \leq h < k \leq 1000
  • 0 \leq i < l \leq 1000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

a b c d e f
g h i j k l

出力

2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。


入力例 1

0 0 0 4 5 6
2 3 4 5 6 7

出力例 1

Yes

2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。


入力例 2

0 0 0 2 2 2
0 0 2 2 2 4

出力例 2

No

2 つの直方体は面で接していますが、共通部分の体積は 0 です。


入力例 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

出力例 3

Yes

Score : 250 points

Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

  • 0 \leq a < d \leq 1000
  • 0 \leq b < e \leq 1000
  • 0 \leq c < f \leq 1000
  • 0 \leq g < j \leq 1000
  • 0 \leq h < k \leq 1000
  • 0 \leq i < l \leq 1000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

a b c d e f
g h i j k l

Output

Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.


Sample Input 1

0 0 0 4 5 6
2 3 4 5 6 7

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.


Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.


Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes