【AtCoder】ABC 361 B - Intersection of Cuboids | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 299

問題概要

$xyz$ 空間内において2点 $(a, b, c), \, (d, e, f)$ を結ぶ線分を対角線とし、全ての面が $xy, yz, zx$ 平面上のいずれかに平行な直方体を $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$

考察

サンプルケース1のところに図が掲載されているので多少考えやすいが、やはり空間上で物事を考えると混乱しやすい。ここは次元を落として1次元の問題として次を考えてみよう。

$x$ 軸上に2点 $(a), (b)$ を結ぶ線分を $l(a, b)$ と書く。2つの線分 $l(a,b), \, l(c, d)$ が共通部分を持つか判定せよ ( $a, b, c, d > 0$ ) 。

これは絵を描いて $l(a, b)$ を固定したうえで $l(c, d)$ を左右に動かしてみればすぐに解決する。2つの線分の左側と右側の点それぞれに注目し、 $x_1 = \max(a, c), \: x_2 = \min(b, d)$ としたとき、

$x_1 < x_2 \implies$ 共通部分を持つ
$x_1 \geq x_2 \implies$ 共通部分を持たない

と定式化できる。

同じことを $y, z$ 軸に対しても行えばよい。実装に関してはコードを参照のこと。

コード

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

int main()
{
    int a, b, c, d, e, f, g, h, i, j, k, l;
    cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j >> k >> l;

    int x1 = max(a, g);
    int y1 = max(b, h);
    int z1 = max(c, i);
    int x2 = min(d, j);
    int y2 = min(e, k);
    int z2 = min(f, l);

    if (x1 < x2 && y1 < y2 && z1 < z2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}