This page is still under construction.

Parts of this page are still being built. What you see may change.

Forest for the Trees

Time limit1sMemory limit512 MB

Summary
Given Belle's point and an axis-aligned rectangle of removed trees on the positive lattice, decide whether any remaining lattice point blocks the segment from the origin and report the closest blocker.
Level

Medium7 of 10

Topics
Number theory, Geometry, Math, Implementation
Solved
No attempts yet

Problem

You are playing hide-and-go-seek in a forest with Belle. The forest has one tree at each of the positive integer lattice points. That is, there is a tree at every point (x,y)(x,y) where xx and yy are both positive integers. You may consider each tree as a point. A logging company has cut down all of the trees in some axis-aligned rectangle, including those on the boundary of the rectangle.

You are standing at (0,0)(0,0) and Belle is standing at (x_b,y_b)(x\_b,y\_b). You can see Belle if and only if there is no tree blocking your line of sight to Belle. If there is a tree at (x_b,y_b)(x\_b,y\_b), Belle will make it easier for you to find her by standing on the side of the tree facing your location.

For example, suppose that Belle is standing at (2,6)(2,6). If the trees in the rectangle with corners at (1,1)(1,1) and (5,4)(5,4) are cut down (blue rectangle in figure), then you can see Belle. However, if the rectangle was at (3,5)(3,5) and (5,7)(5,7) (red rectangle in figure), then the tree at (1,3)(1,3) would be in the way.

Given the rectangle and Belle's location, can you see her?

Input

The first line of input contains two integers x_bx\_b and y_by\_b (1≤x_b,y_b≤10121 \leq x\_b,y\_b \leq 10^{12}), which are the coordinates that Belle is standing on.

The second line of input contains four integers x_1x\_1, y_1y\_1, x_2x\_2 and y_2y\_2 (1≤x_1≤x_2≤10121 \leq x\_1 \leq x\_2 \leq 10^{12} and 1≤y_1≤y_2≤10121 \leq y\_1 \leq y\_2 \leq 10^{12}), which specify two opposite corners of the rectangle at (x_1,y_1)(x\_1, y\_1) and (x_2,y_2)(x\_2, y\_2).

Output

If you can see Belle, display Yes.

Otherwise, display No and the coordinates of the closest tree that is blocking your view.

Examples3

  1. Example 1

    Input
    2 6
    1 1 5 4
    
    Expected output
    Yes
    
  2. Example 2

    Input
    2 6
    3 5 5 7
    
    Expected output
    No
    1 3
    
  3. Example 3

    Input
    830844890448 39710592053
    821266 42860 402207107926 423171345006
    
    Expected output
    No
    402207964848 19223704203