Farthest Positive Ray Intersection
Autumn Tournament (2012)
Submission name: lines.cpp
Problem summary
Given rays y=A*x+B for x>0, answer the largest positive x-coordinate where a query line intersects any ray. Queries are XOR-obfuscated according to whether the previous answer existed.
Input
N; N coefficient pairs A B; Q; Q encoded pairs E F. Decode C,D directly after a successful query (also for the first query); otherwise XOR both with2^29−1.
Output
For each query print the largest positive intersection to at least six decimal places, or No cross.
Constraints
N,Q<50001;distinct slopes;coefficient magnitudes<10^9;query slopes differ from all ray slopes and query intercepts differ from all ray intercepts.
Worked example
An independently prepared worked example; constructive outputs may have other valid forms.
Input
2 4 2 -1 0 3 -5 3 0 1 -5 3
Output
0.75000000 No cross 1.00000000
Solution analysis
- For slopes A<C, each ray minus the query is strictly decreasing. The last intersection among these rays is where their upper envelope meets the query. Sort rays by slope and build the upper convex envelope for every prefix. Each new line pops obsolete envelope suffixes, but keep popped nodes so older versions remain available.
- A node stores its predecessor and the rational x-coordinate where it becomes the best line. Binary-lifting predecessor pointers permit a logarithmic search along any historical envelope. At a node activation point, evaluate the sign of envelope-minus-query using integer cross multiplication, avoiding fragile floating-point envelope comparisons.
- Restrict to the prefix A<C using lower_bound. Along its envelope the sign eventually changes from positive to negative because every slope is smaller than C. Find the envelope segment containing that crossing, then compute its line-intersection formula in long double. Repeat with all coefficients negated to handle A>C using a lower envelope of the original rays.
- In the example the first query intersects y=4x+2 at3/4, while its other intersection is negative. The second query has no positive intersection. Therefore the third encoded pair must be XOR-decoded and has a different meaning from the first despite identical encoded input.
Why it works
Each envelope represents the pointwise maximum of precisely its slope prefix. Its difference from the query is strictly decreasing, so the activation-point sign changes at most once and binary lifting locates the correct segment. Negation gives the symmetric slope side. Taking the larger positive result covers every ray.
Watch out. Decode from whether the previous query had a positive intersection, not from its numeric value. Exclude x≤0. Keep persistent predecessors instead of destructively discarding old hull versions. Signed64-bit products are safe for the stated coefficient bounds.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each envelope represents the pointwise maximum of precisely its slope prefix. Its
// difference from the query is strictly decreasing, so the activation-point sign changes at most once
// and binary lifting locates the correct segment.
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
struct Hull{
static const int LOG=17;
vector<long long>slope,intercept,numerator,denominator;
vector<vector<int>>up;
Hull(vector<pair<long long,long long>>lines){
sort(lines.begin(),lines.end());
int n=lines.size();
slope.resize(n);
intercept.resize(n);
numerator.resize(n);
denominator.resize(n);
up.assign(LOG,vector<int>(n,-1));
int last=-1;
for(int i=0;i<n;i++){
slope[i]=lines[i].first;
intercept[i]=lines[i].second;
int previous=last;
while(previous>=0&&denominator[previous]!=0){
long long num=intercept[previous]-intercept[i];
long long den=slope[i]-slope[previous];
if(num*denominator[previous]>numerator[previous]*den){
break;
}
previous=up[0][previous];
}
up[0][i]=previous;
if(previous>=0){
numerator[i]=intercept[previous]-intercept[i];
denominator[i]=slope[i]-slope[previous];
}
for(int bit=1;bit<LOG;bit++){
int middle=up[bit-1][i];
if(middle>=0){
up[bit][i]=up[bit-1][middle];
}
}
last=i;
}
}
long double query(long long c,long long d)const{
int v=lower_bound(slope.begin(),slope.end(),c)-slope.begin()-1;
if(v<0){
return -1;
}
auto negative=[&](int node){
if(denominator[node]==0){
return false;
}
long long value=(slope[node]-c)*numerator[node]+(intercept[node]-d)*denominator[node];
return value<0;
};
if(negative(v)){
for(int bit=LOG-1;bit>=0;bit--){
int previous=up[bit][v];
if(previous>=0&&negative(previous)){
v=previous;
}
}
v=up[0][v];
}
return static_cast<long double>(d-intercept[v])/(slope[v]-c);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<pair<long long,long long>>lines(n),negated(n);
for(int i=0;i<n;i++){
cin>>lines[i].first>>lines[i].second;
negated[i]={-lines[i].first,-lines[i].second};
}
Hull upper(lines),lower(negated);
int q;
cin>>q;
bool previousExists=true;
cout<<fixed<<setprecision(8);
while(q--){
long long c,d;
cin>>c>>d;
if(!previousExists){
c^=(1LL<<29)-1;
d^=(1LL<<29)-1;
}
long double answer=max(upper.query(c,d),lower.query(-c,-d));
previousExists=answer>0;
if(previousExists){
cout<<answer<<'\n';
}
else{
cout<<"No cross\n";
}
}
}