Forest for the Trees
Time limit1sMemory limit512 MB
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 where and 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 and Belle is standing at . 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 , 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 . If the trees in the rectangle with corners at and are cut down (blue rectangle in figure), then you can see Belle. However, if the rectangle was at and (red rectangle in figure), then the tree at 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 and (), which are the coordinates that Belle is standing on.
The second line of input contains four integers , , and ( and ), which specify two opposite corners of the rectangle at and .
Output
If you can see Belle, display Yes.
Otherwise, display No and the coordinates of the closest tree that is blocking your view.