탈출 불가능한 미로

시간 제한1초메모리 제한1024 MB

요약
직사각형 안에 수평, 수직 선분 벽들이 있을 때 (s,1)에서 (e,H-1)까지 벽에 닿지 않고 갈 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
유니온 파인드, 기하, 정렬, 그래프
정답자
아직 제출이 없습니다

문제

준혁이는 좌표평면 위에 네 점 (0,0)(0,0), (W,0)(W,0), (0,H)(0,H), (W,H)(W,H)을 꼭짓점으로 한 안이 비어있는 직사각형 테두리를 그렸다.

이 사각형 위에 xx축과 평행한 선분을 NN개, yy축과 평행한 선분을 MM개 추가하여 미로를 만드려고 한다.

미로는 출발점 (s,1)(s,1)에서 출발하여 도착점인 (e,H−1)(e,H-1)까지 준혁이가 그린 직사각형이나 선분을 접하거나 지나지 않고 도달할 수 있다면 탈출 가능하다. 즉 (s,1)(s,1)에서 시작하고 (e,H−1)(e,H-1)에서 끝나는 사각형 테두리 혹은 선분을 접하거나 지나지 않는 곡선이 존재한다면, 탈출 가능하다.

하지만 너무 선분을 많이 그려버린 준혁이는 미로가 탈출할 수 있는지 한 눈에 알 수 없어졌다. 준혁이가 만든 미로가 탈출 가능한 미로인지 확인해보자.

입력

첫째 줄에 NN, MM, WW, HH가 공백으로 구분되어 주어진다. (0≤N,M≤200,000(0 \leq N, M \leq 200\\,000; 2≤W,H≤100,000)2\leq W,H \leq 100\\,000)

둘째 줄에 출발점과 도착점의 정보 ss, ee가 공백으로 구분되어 주어진다. (0<s,e<W)(0 < s, e < W)

다음 NN개의 줄에 (x_1,y)(x\_1, y) 과 (x_2,y)(x\_2, y)를 잇는 선분인 x_1x\_1, x_2x\_2, yy가 공백으로 구분되어 주어진다. (0≤x_1<x_2≤W(0 \leq x\_1 < x\_2\leq W; 0≤y≤H0 \leq y \leq H)

다음 MM개의 줄에 (x,y_1)(x, y\_1) 과 (x,y_2)(x, y\_2)를 잇는 선분인 y_1y\_1, y_2y\_2, xx가 공백으로 구분되어 주어진다. (0≤y_1<y_2≤H(0 \leq y\_1 < y\_2\leq H; 0≤x≤W0 \leq x \leq W)

주어지는 모든 수는 정수이다.

주어지는 선분은 미로의 출발점이나 도착점과 접하거나 만나지 않는다.

출력

만약 주어진 미로가 탈출 가능하다면 Yes, 아니라면 No를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    2 1 3 5
    1 2
    0 2 2
    1 3 3
    4 5 1
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    0 1 4 4
    1 3
    0 4 2
    
    예상 출력
    No