Intersection of Two Segments
National Olympiad — Municipal round
Submission name: segments.cpp
Problem summary
Two closed segments on the number line have integer endpoints a,b and c,d, which may be given in either order. Find the length of their intersection, or report no intersection.
Input
Four integers a b c d.
Output
Intersection length, or −1 if the segments have no common point.
Constraints
−100≤a,b,c,d≤100.
Worked example
An independently prepared example for this explanation.
Input
7 2 4 9
Output
3
Solution analysis
- Normalize each endpoint pair.
- The intersection starts at the larger left endpoint and ends at the smaller right endpoint.
- A reversed intersection is empty; equal endpoints mean length zero.
Why it works
A point is in both closed segments precisely when it is at least both left endpoints and at most both right endpoints.
Complexity: O(1) time and space.
Watch out. A single shared endpoint gives 0, not −1.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A point is in both closed segments precisely when it is at least both left endpoints and
// at most both right endpoints.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a>b){
swap(a,b);
}
if(c>d){
swap(c,d);
}
int l=max(a,c),r=min(b,d);
cout<<(l>r?-1:r-l)<<'\n';
}