Proficient.
Put your skills to the test.

Problem summary

Find the minimum Manhattan distance between points on two axis-parallel closed segments.

Constraints

Coordinates are positive integers below 100; each segment is axis-parallel.

Worked example

An independently prepared example for this explanation.

4 2 4 4
6 6 2 6

2

Solution analysis

1. Project each segment onto the x and y axes, normalizing the endpoint order. A vertical or horizontal segment is exactly the Cartesian product of these intervals, one of which has zero length.
2. The minimum gap between two closed intervals [a,b],[c,d] is max(0,c−b,a−d). Sum the independent x and y gaps.
3. In the first example, the vertical segment has x=4 and y∈[2,4]; the horizontal one has x∈[2,6] and y=6. The x projections overlap, while the y gap is 2, so their distance is 2.

Why it works

Manhattan distance is the sum of an x-coordinate difference and a y-coordinate difference. Because each segment is a Cartesian product, independently minimizing those two terms yields coordinates that belong to their respective segments. Therefore the sum of projection gaps is both a lower bound and attainable.

Watch out. Do not use Euclidean distance. Overlapping projections contribute zero, and endpoint order is arbitrary.

An independently written complete program with standard headers.

#include<iostream>
#include<algorithm>
// Algorithm: Project each segment onto the x and y axes, normalizing the endpoint order.
using namespace std;
int gap(int a,int b,int c,int d){
    return max({0,c-b,a-d});
}
int main(){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    cout<<gap(min(x1,x2),max(x1,x2),min(x3,x4),max(x3,x4))+
            gap(min(y1,y2),max(y1,y2),min(y3,y4),max(y3,y4))
            <<'\n';
}