img
Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
Mirrority Report
report.c, report.cpp, Report.java, report.py
In the physics class, each student has to complete a semestral work. You chose to work on an
experiment which examines the properties of rare unstable particles, known as red balls. A red
ball particle travels in a straight line until it is reflected by a mirror.
Our experiment can be thought of as several one-reflection mirrors, which can be treated as
(potentially infinite) lines in a 2D plane. A one-reflection mirror is made in a way that it reflects
a particle only for the first time the mirror is hit by the particle, no matter which direction the
particle is coming from. After that, the mirror will always let that particle pass through.
When reflecting, the angle of the line along which the particle approaches the point of reflection
is equal to the angle of the line along which the particle leaves the point of reflection, when both
angles are measured to the normal of the reflecting mirror. The particle disintegrates if it gets
to a crossing point of two mirrors which would otherwise reflect it.
The mirror layout was created by your teacher and your task is to find directions which cause
a particle launched from its given starting location to reach a specified final location.
Input Specification
The first input line contains a nonnegative integer N (0 N 8), the number of mirrors. The
second input line contains four integers Sx, Sy , Ex, Ey , the coordinates of the starting location
and the final location. Each of the next N lines contains four integers Ax, Ay , Bx, By , describing
two points which define the line of the i-th mirror.
All input coordinates are between -100 and 100, inclusively. The starting and the final locations
are different. The distance of both starting and final location from any mirror is nonzero.
It is guaranteed that the input does not require a valid solution to reflect the particle closer
than 10-4 from any crossing point of the reflecting mirror with any other mirror that could still
reflect the particle.
Output Specification
Output one line with one integer, the number of distinct launch directions from the starting
location which make the particle reach the final location.
img
Output for Sample Input 1
Sample Input 1
1
2
2342
2233
1434
Output for Sample Input 2
Sample Input 2
1
3
2
3
5
2
1
3
1
1
2
4
4
2
5
4
6
5
Sample Input 3
Output for Sample Input 3
1
2
0040
0444
start
start
end
end
start
end
Figure 1: Illustration of Sample Inputs 1, 2, and 3.