Find a Ray through One-Sided Mirrors
Autumn Tournament (2008)
Submission name: mirrors.cpp
Problem summary
A light ray must travel from A to B while reflecting exactly once from each of N disjoint mirror segments, in any order. Each segment is directed from its first endpoint to its second: its left face reflects, while its right face is transparent. Contact with an endpoint is allowed, and sliding along a mirror counts as a reflection. Determine whether a suitable initial direction exists and report its counterclockwise angle from the positive x-axis.
Source clarification. Restored from retained completed-algorithm notes and the original statement after workspace maintenance. Prior version passed all21 official mirror input/allowed-angle cases; this reconstructed source receives fresh strict-build/sample checks separately. No downloaded reference program was executed.
Input
N; then Ax Ay; then Bx By; then N lines x1 y1 x2 y2 describing directed mirror segments.
Output
NO if impossible. Otherwise YES on one line and a valid initial angle in degrees, between0 and360 inclusive, on the next, printed with six decimal places.
Constraints
1≤N≤10. Coordinates are real, have at most six decimal places, and absolute value≤10000. Mirror lengths≥0.001. Segments do not intersect, and A and B lie on no mirror.
Worked example
Original sample; the ray reaches the two reflecting faces in turn. More than one valid angle is permitted when it exists; this implementation prints the shown angle for the displayed input.
Input
2 0 0 0 5 1 0 1 2 -1 4 -1 2
Output
YES 51.340192
Solution analysis
- First imagine the order of reflections were known. Reflect the destination across the final mirror line, then across the preceding mirror line, and so on backwards. A reflected ray becomes a straight line in this unfolded geometry. Therefore A must initially point toward the final image of B. This supplies a finite candidate direction for each order; we need not search over arbitrary real angles.
- Enumerate unused mirrors in reverse order with depth-first search. An outgoing ray must lie on the reflecting left side, so the current target image must be on or to the left of the next chosen directed line. Reject orders that fail this cross-product test, then reflect the image across the infinite supporting line. At depth N the image defines a candidate direction from A. Unfolding uses lines only, so the candidate still requires verification against the finite segments.
- Trace that candidate through the actual mirror system. For every segment, solve ray/segment intersection using cross products. Accept only nonnegative forward intersections within the segment, including endpoints, and only approaches from the reflecting left face. A crossing from the transparent right face does not alter the ray. Choose the nearest actual reflecting contact; ignoring this nearest-hit rule could incorrectly jump through another mirror.
- After a contact, reflect the unit direction d across the mirror unit tangent u using 2u(d·u)−d. Track a bitmask of already contacted mirrors and reject a repeated reflection. When all N are visited, accept B only if it is on the current forward ray and before the next reflecting contact. A collinear overlap is a special case: count the slide once, advance to the far endpoint, and keep the direction. Skip only the immediately previous surface to avoid numerical self-intersection at the starting contact.
- Worked example: A=(0,0), B=(0,5), with upward mirror(1,0)→(1,2) and downward mirror(−1,4)→(−1,2). Reflect B across the second supporting line to(−2,5), then across the first to(4,5). The initial vector is(4,5), angle atan2(5,4)=51.340192°. Physical tracing verifies both finite reflecting faces and the final target.
- Use long double and normalized mirror tangents for stable side tests. Reflection across a line is computed by projecting the point onto that line and taking twice the projection minus the point. Geometry tolerances are small compared with the source precision, but exact equality should never decide parallelism or endpoint membership. Output any verified direction rather than assuming a guessed reflection order really occurs.
Why it works
Every valid ray has an order of N distinct reflecting contacts. Reversely reflecting B along this order unfolds the specular path into a straight ray from A, so the search enumerates its candidate direction. The left-face pruning is necessary for any such valid reflection. Conversely, acceptance comes only from a physical nearest-contact trace that respects segment bounds, transparent backs, all reflection laws and the no-repeat mask, then reaches B after all N contacts. Thus every accepted direction is valid, and every valid order has its candidate considered; collinear sliding is separately counted as required.
Watch out. The left/right orientation depends on endpoint order. Transparent back-face crossings are not reflections. Unfolding infinite lines alone does not prove a ray hits finite segments. Always choose the nearest reflecting hit, include endpoint contacts, and handle collinear sliding explicitly. Do not count the same surface twice due to floating-point self-contact. atan2 returns radians and may be negative; convert and normalize before printing.
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;
const long double EPS=1e-11L;
struct Point{
long double x;
long double y;
};
Point operator+(Point a,Point b){
return {a.x+b.x,a.y+b.y};
}
Point operator-(Point a,Point b){
return {a.x-b.x,a.y-b.y};
}
Point operator*(Point a,long double factor){
return {a.x*factor,a.y*factor};
}
long double dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
long double cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
long double length(Point a){
return sqrtl(dot(a,a));
}
struct Mirror{
Point a;
Point b;
Point unit;
};
int n;
Point sourcePoint,targetPoint;
vector<Mirror>mirrors;
Point reflectPoint(Point point,const Mirror&mirror){
Point offset=point-mirror.a;
Point projection=mirror.a+mirror.unit*dot(offset,mirror.unit);
return projection*2-point;
}
bool reachesTarget(Point initialDirection){
long double size=length(initialDirection);
if(size<EPS){
return false;
}
Point direction=initialDirection*(1/size);
Point origin=sourcePoint;
int used=0;
int previous=-1;
for(int step=0;step<=n;++step){
long double nearest=numeric_limits<long double>::infinity();
long double slideExit=0;
int chosen=-1;
bool grazing=false;
for(int i=0;i<n;++i){
if(i==previous){
continue;
}
const Mirror&mirror=mirrors[i];
Point segment=mirror.b-mirror.a;
long double determinant=cross(direction,segment);
long double distance;
long double exitDistance=0;
bool slide=false;
if(abs(determinant)>EPS){
// Approaching from the transparent right face does not reflect.
if(cross(mirror.unit,direction)>=-EPS){
continue;
}
distance=cross(mirror.a-origin,segment)/determinant;
long double fraction=cross(mirror.a-origin,direction)/determinant;
if(distance<=EPS||fraction<-EPS||fraction>1+EPS){
continue;
}
}
else{
if(abs(cross(mirror.a-origin,direction))>EPS){
continue;
}
long double first=dot(mirror.a-origin,direction);
long double second=dot(mirror.b-origin,direction);
long double low=min(first,second);
long double high=max(first,second);
if(high<=EPS){
continue;
}
distance=max(low,0.0L);
exitDistance=high;
slide=true;
}
if(distance<nearest){
nearest=distance;
chosen=i;
grazing=slide;
slideExit=exitDistance;
}
}
Point toTarget=targetPoint-origin;
long double targetDistance=dot(toTarget,direction);
if(used==(1<<n)-1&&targetDistance>=-EPS&&abs(cross(toTarget,direction))<=1e-8L&&
targetDistance<nearest+EPS){
return true;
}
if(chosen<0||(used&(1<<chosen))){
return false;
}
used|=1<<chosen;
if(grazing){
// Sliding along a segment counts once; continue from its far end.
origin=origin+direction*slideExit;
}
else{
origin=origin+direction*nearest;
Point unit=mirrors[chosen].unit;
direction=unit*(2*dot(direction,unit))-direction;
}
previous=chosen;
}
return false;
}
long double answerAngle;
bool searchImages(Point image,int mask){
if(mask==(1<<n)-1){
Point direction=image-sourcePoint;
if(!reachesTarget(direction)){
return false;
}
answerAngle=atan2l(direction.y,direction.x)*180/acosl(-1);
if(answerAngle<0){
answerAngle+=360;
}
return true;
}
for(int i=0;i<n;++i){
if(mask&(1<<i)){
continue;
}
// Reverse unfolding must leave the reflected image on the front side.
if(cross(mirrors[i].unit,image-mirrors[i].a)<-EPS){
continue;
}
if(searchImages(reflectPoint(image,mirrors[i]),mask|(1<<i))){
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>sourcePoint.x>>sourcePoint.y>>targetPoint.x>>targetPoint.y;
mirrors.resize(n);
for(Mirror&mirror:mirrors){
cin>>mirror.a.x>>mirror.a.y>>mirror.b.x>>mirror.b.y;
Point segment=mirror.b-mirror.a;
mirror.unit=segment*(1/length(segment));
}
if(searchImages(targetPoint,0)){
cout<<"YES\n"<<fixed<<setprecision(6)<<answerAngle<<'\n';
}
else{
cout<<"NO\n";
}
}