Minimum Pairwise Distance in a Reflecting Circular Vessel

Dr. AQ is studying the motion of particles inside a circular vessel. The vessel is given by a circle with center \( (x_0,y_0) \) and radius \( R \) in the Cartesian plane. There are \( n \) particles inside the vessel. The \( i\)-th particle starts at position \( (x_i,y_i) \) at time \( 0 \) and moves with velocity \( (v_{x_i},v_{y_i}) \); if no collision occurs, its position at time \( t \) would be \( (x_i+t\,v_{x_i},\, y_i+t\,v_{y_i}) \). The particles move independently.

When a particle hits the vessel wall (i.e. the circle defined by \( (x-x_0)^2+(y-y_0)^2=R^2 \)), it undergoes a perfectly elastic collision (instantaneous) with mirror reflection. In other words, if \( \mathbf{v} \) is the velocity vector and \( \mathbf{n} \) is the outward unit normal vector at the collision point, then the new velocity becomes \[ \mathbf{v}_{new} = \mathbf{v} - 2(\mathbf{v}\cdot\mathbf{n})\,\mathbf{n}. \] Although the speed is preserved after collision, each collision causes damage to the particle. Specifically, if a particle has collided with the wall \( k \) times, then on its \( k\)-th collision it will vanish immediately.

Dr. AQ wants to determine, over the entire time interval from \( t=0 \) until all particles have disappeared, what is the minimum distance between any two particles at the same moment in time. Can you help him compute this minimum pairwise distance?

inputFormat

The first line contains three space‐separated real numbers: \( x_0\, y_0\, R \) — the center and radius of the circular vessel.

The second line contains an integer \( n \) (\( n\ge2 \)) — the number of particles.

Then \( n \) lines follow. The \( i\)-th line contains five space‐separated numbers: \( x_i\, y_i\, v_{x_i}\, v_{y_i}\, k \). Here \( (x_i,y_i) \) is the initial position of the particle, \( (v_{x_i},v_{y_i}) \) is its velocity vector, and \( k \) (a positive integer) denotes that the particle will vanish when it collides with the wall for the \( k\)-th time.

outputFormat

Output a single real number representing the minimum distance between any two particles (over all times until all particles have vanished). Your answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

0 0 10
2
0 0 1 0 2
0 1 1 0 2

1.000000