Line Through Segments
National Olympiad — National round (2011 season)
Submission name: segments.cpp
Problem summary
Given line segments in the plane, find the greatest number intersected by a single infinite straight line. Touching endpoints counts as intersection.
Input
N followed by N quadruples x1 y1 x2 y2.
Output
The maximum number of intersected segments.
Constraints
1 ≤ N < 100; endpoint coordinates are integers in [−1000,1000].
Worked example
An independently prepared example for this explanation.
Input
3 1 2 1 3 2 100 2 101 3 -100 3 -101
Output
2
Solution analysis
- An optimal line can be translated until it touches a segment endpoint without losing any of its current intersections. Rotate around that endpoint until reaching another endpoint; the intersections stay valid until an endpoint event, and boundary touching is allowed. Thus some optimal line passes through two input endpoints.
- Enumerate all distinct endpoint pairs. For each candidate line compute the signed cross products of both endpoints of every segment relative to it. The segment is intersected exactly when at least one product is zero or the products have opposite signs.
- The sample’s first and second vertical segments can both be intersected by a suitable line, but no line meets all three. Candidate endpoint lines therefore achieve maximum 2. If every endpoint coincides, any line through that point meets every segment.
Why it works
For a line intersecting some chosen set of segments, translation to the boundary of the feasible offset interval yields an endpoint contact. The orientations through that endpoint preserving all chosen intersections form a closed set; at a boundary orientation another endpoint is touched, unless all intersections are automatic for every orientation, in which case any distinct endpoint works. Hence endpoint-pair candidates include an optimum. The opposite-side test is precisely the condition for a segment to cross or touch an infinite line.
Watch out. Skip coincident endpoint pairs, which do not define a line. Avoid multiplying two cross products; compare their signs directly to prevent overflow.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
long long x,y;
};
long long cross(Point a,Point b,Point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
int n;
cin>>n;
vector<Point>endpoints(2*n);
for(Point&p:endpoints){
cin>>p.x>>p.y;
}
int answer=n;
bool defined=false;
for(int a=0;a<2*n;a++){
for(int b=a+1;b<2*n;b++){
if(endpoints[a].x==endpoints[b].x&&endpoints[a].y==endpoints[b].y){
continue;
}
if(!defined){
answer=0;
defined=true;
}
int count=0;
for(int i=0;i<n;i++){
long long first=cross(endpoints[a],endpoints[b],endpoints[2*i]);
long long second=cross(endpoints[a],endpoints[b],endpoints[2*i+1]);
// A crossing or an endpoint touch is an intersection.
if(first==0||second==0||(first<0)!=(second<0)){
count++;
}
}
answer=max(answer,count);
}
}
cout<<answer<<'\n';
}