Two Circular Arcs
National Olympiad — Municipal round
Submission name: two.cpp
Problem summary
Each closed arc runs counterclockwise from its first endpoint to its second on one circle. Endpoint angles are whole degrees. Equal endpoints define a single point, not the entire circle. Determine whether two arcs share any point.
Input
Two lines, each containing an arc’s start and end angles.
Output
1 if the arcs intersect, otherwise 0.
Constraints
All angles are integers from 0 to 359 inclusive.
Worked example
An independently prepared example for this explanation.
Input
350 10 10 20
Output
1
Solution analysis
- An angle p belongs to arc a→b when its counterclockwise displacement from a is no larger than that of b.
- Two closed arcs intersect if an endpoint of either lies on the other. Test all four endpoints.
Why it works
Disjoint endpoints with a nonempty intersection would require the arcs to overlap without entering or leaving each other, impossible for proper closed arcs; singleton arcs are covered by the same containment test.
Watch out. Include touching endpoints and wraparound through zero.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Disjoint endpoints with a nonempty intersection would require the arcs to overlap without
// entering or leaving each other, impossible for proper closed arcs; singleton arcs are covered by the
// same containment test.
#include<iostream>
using namespace std;
bool inside(int a,int b,int p){
return (p-a+360)%360<=(b-a+360)%360;
}
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<(inside(a,b,c)||inside(a,b,d)||inside(c,d,a)||inside(c,d,b))<<'\n';
}