Nearest Point Strictly Outside a Square
National Olympiad — Municipal round (2010 season)
Submission name: remote.cpp
Problem summary
An axis-aligned square has side a and is centred at the origin. Among the given points strictly outside it, minimize |x|+|y|. Output 0 if no point is outside.
Input
n and a, then n integer-coordinate points.
Output
The minimum Manhattan distance of an outside point, or 0.
Constraints
1 ≤ n ≤ 10000; 1 ≤ a ≤ 1000; −100000 ≤ x,y ≤ 100000.
Worked example
Input and output for the worked example discussed below.
Input
5 4 1 2 4 6 -3 2 -2 2 4 -1
Output
5
Solution analysis
- The square includes coordinates satisfying |x|≤a/2 and |y|≤a/2. A point is strictly outside when either comparison fails. Boundary points must be excluded from the candidates.
- Avoid floating-point halves by comparing 2|x|>a or 2|y|>a. For each outside point, compute its Manhattan distance and update the smallest distance seen.
- In the sample, (−3,2) and (4,−1) are outside and both have distance 5; (4,6) has distance 10. The point (−2,2) lies on the square boundary and does not qualify. Thus the answer is 5.
Why it works
The doubled inequalities are algebraically equivalent to the strict outside condition. Every qualifying point is examined once, and the maintained minimum is the smallest distance among exactly those points. If none qualify, the required fallback is zero.
Watch out. Outside uses OR, not AND. Strict inequalities exclude the boundary. Distance is |x|+|y|, not Euclidean distance and not distance to the square itself.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
int count;
int side;
cin>>count>>side;
int answer=numeric_limits<int>::max();
for(int index=0;index<count;index++){
int x;
int y;
cin>>x>>y;
// Doubling handles odd side lengths without floating point.
if(2*abs(x)>side||2*abs(y)>side){
answer=min(answer,abs(x)+abs(y));
}
}
cout<<(answer==numeric_limits<int>::max()?0:answer)<<'\n';
}