아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

나무에 가려진 숲

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

요약
양의 정수 격자에서 벨의 위치와 잘려 나간 나무들의 축 정렬 직사각형이 주어질 때, 원점에서 벨을 잇는 선분을 가리는 남은 격자점이 있는지 판정하고 가장 가까운 가림점을 출력한다.
난이도

보통10점 중 7점

유형
정수론, 기하, 수학, 구현
정답자
아직 제출이 없습니다

문제

Belle과 함께 숲에서 숨바꼭질을 하고 있다. 숲에는 양의 정수 격자점마다 나무가 하나씩 있다. 즉, xx와 yy가 모두 양의 정수인 모든 점 (x,y)(x,y)에 나무가 있다. 각 나무는 점으로 생각해도 된다. 벌목 회사가 어떤 축에 평행한 직사각형 안의 모든 나무를 잘라 냈는데, 직사각형의 경계에 있는 나무도 포함해서 잘라 냈다.

너는 (0,0)(0,0)에 서 있고 Belle은 (x_b,y_b)(x\_b,y\_b)에 서 있다. Belle을 향한 시선을 가리는 나무가 하나도 없을 때, 그리고 그때만 Belle을 볼 수 있다. (x_b,y_b)(x\_b,y\_b)에 나무가 있다면 Belle은 네 위치를 향한 나무의 옆면에 서서 너를 돕는다.

예를 들어 Belle이 (2,6)(2,6)에 서 있다고 하자. (1,1)(1,1)과 (5,4)(5,4)를 꼭짓점으로 하는 직사각형 안의 나무를 잘라 냈다면(그림의 파란 직사각형) Belle을 볼 수 있다. 그러나 직사각형이 (3,5)(3,5)와 (5,7)(5,7)에 있었다면(그림의 빨간 직사각형) (1,3)(1,3)에 있는 나무가 시야를 가린다.

직사각형과 Belle의 위치가 주어질 때, Belle을 볼 수 있는지 판별하라.

입력

첫 번째 줄에는 Belle이 서 있는 좌표인 두 정수 x_bx\_b와 y_by\_b가 주어진다(1≤x_b,y_b≤10121 \leq x\_b,y\_b \leq 10^{12}).

두 번째 줄에는 직사각형의 서로 반대쪽 두 꼭짓점 (x_1,y_1)(x\_1, y\_1)과 (x_2,y_2)(x\_2, y\_2)를 나타내는 네 정수 x_1x\_1, y_1y\_1, x_2x\_2, y_2y\_2가 주어진다(1≤x_1≤x_2≤10121 \leq x\_1 \leq x\_2 \leq 10^{12}, 1≤y_1≤y_2≤10121 \leq y\_1 \leq y\_2 \leq 10^{12}).

출력

Belle을 볼 수 있으면 Yes를 출력한다.

그렇지 않으면 No와 함께 시야를 가리는 가장 가까운 나무의 좌표를 출력한다.

예제3

  1. 예제 1

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

    입력
    2 6
    3 5 5 7
    
    예상 출력
    No
    1 3
    
  3. 예제 3

    입력
    830844890448 39710592053
    821266 42860 402207107926 423171345006
    
    예상 출력
    No
    402207964848 19223704203