Codeforces #587C (1216C) White Sheet

너무 바꿀 필요는 없지만 이 문제는 다음과 같다.

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

한쪽 눈을 뜰 때 무슨 은신법이 있느냐

1: 전혀 흰색을 끼지 않은 경우
이 숨겨진 방식에 전혀 영향을 미치지 않기 때문에 생각하고 싶은 것은 말하지 않아도 안다.

2: 흰색에 완전히 포함된 검은색 의자
직관적으로 두 번째 종이에 흰색을 숨기려면 원래의 사각형을 모두 숨겨야 한다.

3: 완전히 숨겨진 상황
이 경우 두 번째는 아무리 붙여도 완전히 숨겨져 두 번째를 붙이지 않아도 숨길 수 있다.

4: 사각을 두 부분으로 나눌 때
한순간에 두 번째를 어떻게 붙이느냐에 영향을 미치겠지만'다른 장'만 붙기 때문에 원래 네모를 붙이지 않으면 숨길 수 없다

5사각형 모서리를 숨기는 경우

이 경우 두 번째 장의 결과에 영향을 미칠 수 있다.원래 4각에 흰색 점선이 있으면 5의 검은색 4각은 한쪽의 2각을 숨기기 때문에 두 번째 검은색 4각은 적선의 4각을 완전히 숨기려면 숨길 수 있다.

육사각형의 한 귀만 숨길 때

다소 망설이지만 이 사각형을 숨기려면 세로, 가로로 남은 흰색 부분과 같은 이상의 사각형이 없으면 숨길 수 없다.

요점: 검은색 종이가 두 장밖에 없어요.

만약 이 문제가 두 장의 검은색이 아니라 임의의 검은색 종이를 사용한다면 상황은 달라질 것이다.예를 들어 상기 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")