Codeforces #587C (1216C) White Sheet

あまり言い換えの必要もないが、この問題は以下の通りである。

- 白シート、黒シート、黒シートの３つのシートの左下と右上のx,y座標を渡す
- 白->黒->黒の順でシートを張るがこのとき、白のシートが完全に隠れるかを判定せよ
- x,yは x,y < 10^6

１枚目を張ったときにどのような隠れ方があるか

• 1: 全く白にかぶらない場合
  この隠れ方には全く影響しないので考慮したくていいことは自明である。

• 2: 白の中に完全に入っている黒シート
  ２枚目のシートで白を隠すには元の四角すべてを隠さないといけないことは直感的に自明である。

• 3: 完全に隠している場合
  この場合、２枚目をどのように張ったとしても完全に隠れているので、２回目を張るまでもなく隠れる。

• 4: 四角を２分する場合
  一瞬、２枚目のをどのように張るかの結果に影響を及ぼすように思えるが、「もう一枚」しか張れないので元の四角を張らなければ隠せないことが分かる

• 5 四角の一辺を隠す場合
  
  この場合、２枚目の結果に影響を及ぼす。元の四角が白い破線まで存在していた場合、5の黒四角をはある１辺の二角を隠すので、二枚目の黒四角は赤線の四角を完全に隠すのならば隠しきれる。

• 6 四角の１角のみを隠す場合

• 
  多少判断に迷うが、この四角を「もう一枚で」隠すには縦・横が残っている白い部分と同じ以上の四角がなければ隠し切れない。

ポイント：黒い紙は２枚だけであること

もしもこの問題が2枚の黒ではなく、任意枚数の黒い紙を使えるとするならば状況は変わってくる。例えば、上記の２の場合であっても、

次の4枚が赤い領域を隠せば隠し切ることができるので、例えば、白い四角がどのように分割されているか（あるいは黒の四角の合計がどの領域を隠せているか）をしっかりと保持しなければならない。

ポイント：今回の場合

あくまで２枚の黒い紙しか使えないため、上記の区分にしたがえば以下のように

番号	１枚目で隠し切るか	隠しきれる２枚目は何か
1	NO	元の白い四角と同じサイズ
2	NO	元の白い四角と同じサイズ
3	YES	-
4	NO	元の白い四角と同じサイズ
5	NO	隠しきれなかった白い四角を隠せるサイズ
6	NO	元の白い四角と同じサイズ

といえる。

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
x5, y5, x6, y6 = map(int, input().split())
 
def do_mask(x1, y1, x2, y2, x3, y3, x4, y4):
    # もし、既に隠しきられている場合、その旨を返す
    if x1 == -1:
        return -1, -1, -1, -1
    # 全部隠されている場合
    if x3 <= x1 and x2 <= x4 and y3 <= y1 and y2 <= y4:
        return -1, -1, -1, -1
 
    # パターン５で横長に隠す場合
    if x3 <= x1 and x2 <= x4:
        if y3 <= y1 and y1 <= y4:
            y1 = y4
        if y3 <= y2 and y2 <= y4:
            y2 = y3
 
    # パターン５で縦長に隠す場合
    if y3 <= y1 and y2 <= y4:
        if x3 <= x1 and x1 <= x4:
            x1 = x4
        if x3 <= x2 and x2 <= x4:
            x2 = x3
 
    return x1, y1, x2, y2
 
# 1枚目で隠す
x1, y1, x2, y2 = do_mask(x1, y1, x2, y2, x3, y3, x4, y4)
# 2枚目で隠す
x1, y1, x2, y2 = do_mask(x1, y1, x2, y2, x5, y5, x6, y6)
print("NO" if x1 == -1 else "YES")