Jump to a Rectangle
National Olympiad — Municipal round (2015 season)
Submission name: hopper.cpp
Problem summary
Find the smallest integer distance from a given point to any point in or on an axis aligned rectangle.
Input
The point x0 y0, then two opposite rectangle corners x1 y1 and x2 y2.
Output
The smallest integer distance d.
Constraints
All coordinates are integers in [−10^8, 10^8].
Worked example
An independently prepared example for this explanation.
Input
2 1 4 3 7 5
Output
3
Solution analysis
- Normalize both coordinate intervals. The nearest rectangle point clamps the given x and y independently to those intervals. A coordinate already inside its interval contributes zero distance.
- Let dx and dy be the two nonnegative gaps. The squared minimum distance is dx² + dy². Compute its integer square root and round upward, correcting the floating approximation by integer comparisons.
- For (2,1) and rectangle [4,7] × [3,5], the gaps are 2 and 2. The minimum distance is √8; the smallest integer distance attained within the rectangle is 3. Continuity of distance on the rectangle and the existence of an integer-coordinate corner ensure that this ceiling is attained.
Why it works
Independent clamping minimizes the sum of the two squared gaps. Rectangle distances fill an interval because the rectangle is connected and distance is continuous. Its maximum is at least the distance to a farthest corner; in a nondegenerate integer rectangle that maximum is at least the ceiling of the minimum (move one unit away along a coordinate if the minimum is nonintegral). Therefore rounding the minimum upward gives the required attained integer distance.
Watch out. Use 64-bit products. Normalize the corners. Round up only when the squared distance is not a perfect square.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
long long x,y,x1,y1,x2,y2;
cin>>x>>y>>x1>>y1>>x2>>y2;
if(x1>x2){
swap(x1,x2);
}
if(y1>y2){
swap(y1,y2);
}
long long dx=max({x1-x,x-x2,0LL});
long long dy=max({y1-y,y-y2,0LL});
long long squared=dx*dx+dy*dy;
long long answer=static_cast<long long>(sqrt(static_cast<long double>(squared)));
// Integer comparisons remove any rounding error from sqrt.
while(answer*answer<squared){
++answer;
}
while(answer>0&&(answer-1)*(answer-1)>=squared){
--answer;
}
cout<<answer<<'\n';
}