Equal Brightness at Antipodal Sensors
Autumn Tournament (2013)
Submission name: orbit.cpp
Problem summary
Place two sensors on a circle of radius R centered at the origin. Their measured brightness is the maximum contribution L/(4*pi*distance^2) of any star. Find equal-brightness positions with maximum separation.
Source clarification. Brightness is singular if a sensor exactly coincides with a star. The inverse formulation is continuous there, but finite-precision outputs near such configurations need special care; the source does not explicitly exclude stars on the orbit.
Input
N R, followed by N triples x y L.
Output
Four real coordinates X1 Y1 X2 Y2, accepted with absolute or relative error below10^−7. The statement also permits No solution if no suitable pair exists; the antipodal continuity argument shows a pair exists in the nonsingular mathematical setting.
Constraints
N≤100000;R≤10^9;|x|,|y|≤10^9;0<L≤10^9.
Worked example
An independently prepared worked example; constructive outputs may have other valid forms.
Input
1 2 0 0 3
Output
2.000000000000 0.000000000000 -2.000000000000 0.000000000000
Solution analysis
- No two circle points can be farther apart than its diameter2R. It is enough to find an equal-brightness antipodal pair p and−p. Instead of brightness, use inverse brightness u(p)=min(distance(p,star)^2/L). The common4*pi factor can be omitted. This minimum of continuous functions remains continuous even near a star.
- Define h(theta)=u(p(theta))−u(−p(theta)). Advancing the angle by pi swaps the sensors, so h(theta+pi)=−h(theta). The intermediate value theorem gives a zero in every such half-turn bracket. Bisection only needs opposite endpoint signs; h need not be monotone.
- Evaluate u by scanning all stars and computing squared distances directly. Perform100 bisections, retaining the half whose endpoint signs differ. Output one circle point and its exact negation. In the worked example the star is at the origin, so every sensor is distance2 from it: positions(2,0) and(−2,0) have equal brightness and achieve the diameter4.
- If a star lies exactly on the orbit, brightness at that star is singular. Use a non-axis-aligned initial bracket when necessary, and reject zero-distance candidate sensors rather than accepting an undefined brightness as equal. Inverse brightness is used only to find the equal-value pair, not reported as measured brightness.
Why it works
Continuity and the sign reversal guarantee an inverse-brightness equality between antipodal points. For nonsingular sensor positions this is equivalent to equal original maximum brightness. Antipodal positions achieve the largest possible distance2R, proving optimality. Bisection maintains a zero-containing bracket without assuming monotonicity.
Watch out. Take the maximum of star contributions, not their sum. Work with inverse brightness to avoid division by near-zero distances. Do not assume monotonicity. Very near singular configurations remain sensitive to floating-point output precision.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
struct Star{
long double x,y,light;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long double radius;
cin>>n>>radius;
vector<Star>stars(n);
bool axisSingular=false;
for(Star&star:stars){
cin>>star.x>>star.y>>star.light;
if(star.y==0&&fabsl(star.x)==radius){
axisSingular=true;
}
}
auto inverse=[&](long double x,long double y){
long double result=numeric_limits<long double>::infinity();
for(const Star&star:stars){
long double dx=x-star.x;
long double dy=y-star.y;
result=min(result,(dx*dx+dy*dy)/star.light);
}
return result;
};
auto difference=[&](long double angle){
long double x=radius*cosl(angle);
long double y=radius*sinl(angle);
return inverse(x,y)-inverse(-x,-y);
};
auto singular=[&](long double angle){
long double x=radius*cosl(angle);
long double y=radius*sinl(angle);
return inverse(x,y)==0||inverse(-x,-y)==0;
};
const long double pi=acosl(-1.0L);
long double left=axisSingular?0.123456789L:0;
while(singular(left)){
left+=0.137L;
}
long double right=left+pi;
long double leftValue=difference(left);
if(leftValue!=0){
for(int iteration=0;iteration<100;iteration++){
long double middle=(left+right)/2;
// A pole is not a finite-brightness solution. Try another
// interior point while retaining the same sign bracket.
long double fraction=0.381966011250105L;
while(singular(middle)){
middle=left+fraction*(right-left);
fraction*=0.618033988749895L;
}
long double value=difference(middle);
if(value==0){
left=middle;
right=middle;
break;
}
if((value>0)==(leftValue>0)){
left=middle;
leftValue=value;
}
else{
right=middle;
}
}
}
long double x=radius*cosl(left);
long double y=radius*sinl(left);
// Normalize signed zero for clean coordinate output.
long double oppositeX=x==0?0:-x;
long double oppositeY=y==0?0:-y;
cout<<fixed<<setprecision(12);
cout<<x<<' '<<y<<' '<<oppositeX<<' '<<oppositeY<<'\n';
}