The mirror is the ellipse \(4x^2+y^2=100\), except for a very small opening at the top where \(|x|\le 0.01\). The beam starts at \((0,10.1)\), enters through that opening, and its first actual impact on the mirror is \((1.4,-9.6)\). The task is to count how many reflections occur before the beam reaches the opening again and escapes.
This is a deterministic billiard problem inside an ellipse. Once two consecutive points on the path are known, the next segment is forced by the law of specular reflection, so the mathematics is about deriving a stable update rule for one bounce.
Let \(F(x,y)=4x^2+y^2-100\). Every reflection point lies on the curve \(F(x,y)=0\). The key is to express one bounce entirely in terms of the previous point and the current point.
A single point on the ellipse is not enough, because the next bounce depends on the incoming direction. If the last two points are \(P_{k-1}\) and \(P_k\), then the incoming direction at \(P_k\) is
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
So the true state of the system is the ordered pair \((P_{k-1},P_k)\). The implementation stores exactly that pair and updates it after every reflection.
For an implicit curve \(F(x,y)=0\), the gradient is normal to the curve. Here
$$\nabla F(x,y)=(8x,2y).$$
Therefore the normal at \(P_k=(x_k,y_k)\) is \(n=(8x_k,2y_k)\). If \(v_{\mathrm{in}}\) is the incoming direction, the reflected direction is
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
Equivalently, one may normalize \(n\) first and write the usual unit-normal formula. Both forms describe the same line. Geometrically, the tangential component is preserved and the normal component is reversed, which is exactly the law of reflection.
Starting from the current impact point \(P_k=(x_k,y_k)\), the outgoing ray is
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
Substituting this into the ellipse equation gives
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
Because \(P_k\) already lies on the ellipse, the constant term vanishes, so the quadratic factorizes as
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
The root \(t=0\) is the current point. The other root is the next impact point:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
This simplification is the reason the implementations do not need a general quadratic formula. They only compute the nonzero root and step directly to the next reflection.
The beam arrives from \(P_{-1}=(0,10.1)\) to \(P_0=(1.4,-9.6)\), so
$$v_{\mathrm{in}}=(1.4,-19.7).$$
At \(P_0\), the normal is
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
Applying the reflection formula gives the outgoing direction
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
Then
$$t\approx 0.3275153751,$$
and the next point is
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
This concrete first step is a useful checkpoint because all three implementations reproduce it.
The mirror is missing a tiny arc near the top. On the ellipse, any point with \(|x|\le 0.01\) and \(y>0\) lies on that upper opening rather than on reflective material. So the simulation stops as soon as the next would-be impact satisfies
$$|x|\le 0.01,\qquad y>0.$$
The last counted reflection is the bounce that sends the beam toward that gap. For the given initial ray, the total number of reflections is \(354\).
The C++, Python, and Java implementations store the previous point \((0,10.1)\), the current point \((1.4,-9.6)\), and a counter initialized to zero. That setup means the first loop iteration computes the reflection at the first interior impact point.
Each iteration performs the same four geometric steps: build the incoming vector from the two stored points, compute the normal at the current impact point, reflect the direction, and use the nonzero root above to jump to the next point on the ellipse. After that, the state is shifted forward by replacing the previous point with the current one and the current point with the newly found point.
The C++ implementation uses the unnormalized form \(v-2(v\cdot n)n/(n\cdot n)\), while the Python and Java implementations normalize the normal first. These are algebraically equivalent. After each update the counter is incremented, and the new point is tested against the opening condition. When the test succeeds, the loop stops and prints \(354\).
If the beam reflects \(B\) times before leaving, the running time is \(O(B)\), because every iteration uses only a fixed number of arithmetic operations. Memory usage is \(O(1)\): the algorithm keeps only a few floating-point coordinates, one direction vector, and the reflection counter.
For this specific problem \(B=354\), so the computation is tiny. The important point is not asymptotic difficulty but deriving a numerically stable geometric update that follows the exact reflection law.
Der Spiegel ist die Ellipse \(4x^2+y^2=100\), nur ganz oben fehlt ein winziger Abschnitt mit \(|x|\le 0{,}01\). Der Laser startet bei \((0,10.1)\), tritt durch diese Öffnung ein und trifft den Spiegel zuerst bei \((1.4,-9.6)\). Gesucht ist die Anzahl der Reflexionen, bevor der Strahl die obere Öffnung wieder erreicht und austritt.
Mathematisch ist das ein deterministisches Billardproblem in einer Ellipse. Sobald zwei aufeinanderfolgende Punkte der Bahn bekannt sind, ist der nächste Punkt durch das Reflexionsgesetz eindeutig festgelegt. Deshalb besteht die eigentliche Arbeit darin, eine saubere Formel für genau einen Sprung herzuleiten.
Setze \(F(x,y)=4x^2+y^2-100\). Jeder Reflexionspunkt liegt auf der Kurve \(F(x,y)=0\). Die gesamte Herleitung beschreibt einen Schritt allein mit dem vorherigen und dem aktuellen Treffpunkt.
Ein einzelner Punkt auf der Ellipse genügt nicht, weil die nächste Reflexion von der Einfallsrichtung abhängt. Sind die letzten beiden Punkte \(P_{k-1}\) und \(P_k\), dann ist die einfallende Richtung in \(P_k\)
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
Der Zustand des Systems ist also das geordnete Paar \((P_{k-1},P_k)\). Genau diese beiden Punkte speichern die Implementierungen fortlaufend.
Für eine implizit gegebene Kurve \(F(x,y)=0\) steht der Gradient senkrecht auf der Kurve. Hier gilt
$$\nabla F(x,y)=(8x,2y).$$
Am Punkt \(P_k=(x_k,y_k)\) ist also \(n=(8x_k,2y_k)\) ein Normalenvektor. Mit der einfallenden Richtung \(v_{\mathrm{in}}\) erhält man die reflektierte Richtung durch
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
Man kann \(n\) vorher normieren oder direkt diese unnormierte Form benutzen; geometrisch ist beides identisch. Die Tangentialkomponente bleibt erhalten, die Normalkomponente wechselt ihr Vorzeichen. Genau das ist das Spiegelgesetz.
Vom aktuellen Treffpunkt \(P_k=(x_k,y_k)\) aus hat der reflektierte Strahl die Form
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
Setzt man das in die Ellipsengleichung ein, so erhält man
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
Weil \(P_k\) bereits auf der Ellipse liegt, verschwindet der konstante Term, also faktorisiert das Polynom zu
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
Die Lösung \(t=0\) beschreibt den aktuellen Punkt. Die andere Lösung ist der nächste Treffpunkt:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
Gerade diese Vereinfachung benutzen die Implementierungen: statt einer allgemeinen quadratischen Gleichung wird direkt die nichttriviale Nullstelle berechnet.
Der Strahl kommt von \(P_{-1}=(0,10.1)\) nach \(P_0=(1.4,-9.6)\). Damit ist
$$v_{\mathrm{in}}=(1.4,-19.7).$$
Am Punkt \(P_0\) ist der Normalenvektor
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
Aus der Reflexionsformel folgt
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
Dann ergibt sich
$$t\approx 0.3275153751,$$
und damit
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
Dieser erste Schritt ist ein nützlicher Kontrollpunkt, weil alle drei Implementierungen genau denselben Wert liefern.
Oben fehlt kein Punkt, sondern ein winziger Bogenabschnitt. Auf der Ellipse bedeutet \(|x|\le 0{,}01\) zusammen mit \(y>0\), dass der Strahl die obere Öffnung und nicht reflektierendes Material erreicht. Deshalb endet die Simulation, sobald der nächste potenzielle Treffpunkt die Bedingung
$$|x|\le 0.01,\qquad y>0$$
erfüllt. Die letzte gezählte Reflexion ist also genau diejenige, die den Strahl in Richtung des Spalts schickt. Für die vorgegebenen Startdaten sind es insgesamt \(354\) Reflexionen.
Die C++-, Python- und Java-Implementierungen speichern zu Beginn den vorherigen Punkt \((0,10.1)\), den aktuellen Punkt \((1.4,-9.6)\) und einen Zähler mit Startwert null. Dadurch berechnet die erste Schleifenrunde sofort die Reflexion am ersten inneren Auftreffpunkt.
In jeder Runde werden dieselben vier Schritte ausgeführt: Einfallsvektor aus den beiden gespeicherten Punkten bilden, Normalenvektor am aktuellen Punkt berechnen, Richtung reflektieren und anschließend mit der nichttrivialen Nullstelle direkt zum nächsten Ellipsenpunkt springen. Danach werden die beiden Zustandswerte um eins nach vorne geschoben.
Die C++-Version verwendet die unnormierte Formel \(v-2(v\cdot n)n/(n\cdot n)\), während Python und Java den Normalenvektor zuerst normieren. Algebraisch ist das dieselbe Gerade. Nach jedem Schritt wird der Zähler erhöht und der neue Punkt gegen die Austrittsbedingung geprüft. Beim ersten Treffer in der Öffnung endet die Schleife mit dem Wert \(354\).
Reflektiert der Strahl vor dem Austritt \(B\)-mal, dann beträgt die Laufzeit \(O(B)\), denn pro Schleife fallen nur konstant viele Fließkommaoperationen an. Der Speicherbedarf ist \(O(1)\): gespeichert werden nur einige Koordinaten, ein Richtungsvektor und der Zähler.
Für diese konkrete Aufgabe ist \(B=354\), also ist die Rechnung sehr klein. Entscheidend ist hier nicht die asymptotische Größe, sondern die geometrisch korrekte und numerisch stabile Herleitung des nächsten Auftreffpunkts.
Ayna, \(4x^2+y^2=100\) elipsidir; yalnızca tepe noktasında \(|x|\le 0.01\) aralığına karşılık gelen çok dar bir açıklık vardır. Lazer \((0,10.1)\) noktasından gelip bu açıklıktan içeri girer ve aynaya ilk kez \((1.4,-9.6)\) noktasında çarpar. Amaç, ışın yeniden üst açıklığa ulaşıp dışarı çıkana kadar kaç yansıma olduğunu saymaktır.
Bu problem özünde elips içinde deterministik bir ışın izleme problemidir. Yol üzerindeki ardışık iki nokta bilindiğinde, bir sonraki parça yansıma yasasıyla tamamen belirlenir. Bu yüzden çözümün kalbi, tek bir sekmeyi kapalı biçimde yazabilmektir.
\(F(x,y)=4x^2+y^2-100\) tanımını yapalım. Her yansıma noktası \(F(x,y)=0\) eğrisi üzerindedir. Tüm türetim, bir adımı yalnızca önceki nokta ile mevcut nokta cinsinden yazmaya dayanır.
Elips üzerindeki tek bir nokta yeterli değildir; çünkü sonraki çarpışma geliş yönüne bağlıdır. Son iki nokta \(P_{k-1}\) ve \(P_k\) ise, \(P_k\) noktasındaki geliş doğrultusu
$$v_{\mathrm{in}}=P_k-P_{k-1}$$
olur. Dolayısıyla sistemin gerçek durumu \((P_{k-1},P_k)\) sıralı çiftidir. Uygulamalar da tam olarak bu iki noktayı saklar ve her döngüde ileri taşır.
\(F(x,y)=0\) biçimindeki örtük bir eğri için gradyan eğriye diktir. Bu problemde
$$\nabla F(x,y)=(8x,2y)$$
olduğundan, \(P_k=(x_k,y_k)\) noktasındaki normal vektör \(n=(8x_k,2y_k)\) olur. Geliş yönü \(v_{\mathrm{in}}\) için çıkış yönü
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n$$
formülüyle bulunur. İstenirse önce \(n\) birim uzunluğa indirgenebilir; sonuçta elde edilen doğru aynıdır. Geometrik yorum şudur: teğetsel bileşen korunur, normal bileşen işaret değiştirir.
Mevcut çarpışma noktası \(P_k=(x_k,y_k)\) olsun. Yansıyan ışın
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y)$$
şeklinde parametrelenir. Bunu elips denklemine yerleştirirsek
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100$$
elde edilir. \(P_k\) zaten elips üzerinde olduğu için sabit terim sıfırdır ve denklem şu çarpanlı biçime iner:
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
\(t=0\) mevcut noktayı verir. Diğer kök ise bir sonraki çarpışma noktasıdır:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
Çözümlerde tam olarak bu sadeleşme kullanılır; tam bir ikinci derece formülü çözmek yerine yalnızca sıfır olmayan kök hesaplanır.
Işın \(P_{-1}=(0,10.1)\) noktasından \(P_0=(1.4,-9.6)\) noktasına gelir. Bu yüzden
$$v_{\mathrm{in}}=(1.4,-19.7).$$
\(P_0\) noktasındaki normal
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2)$$
olur. Yansıma formülü uygulanınca
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415)$$
bulunur. Ardından
$$t\approx 0.3275153751$$
ve dolayısıyla
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989)$$
elde edilir. Bu ilk adım iyi bir kontrol noktasıdır; üç dildeki uygulamalar da aynı değeri üretir.
Eksik olan şey tek bir nokta değil, üst taraftaki çok küçük bir yay parçasıdır. Elips üzerindeki bir nokta için \(|x|\le 0.01\) ve \(y>0\) koşulu, ışının yansıtıcı yüzeye değil bu açıklığa ulaştığı anlamına gelir. Bu nedenle simülasyon, sonraki olası çarpışma noktası
$$|x|\le 0.01,\qquad y>0$$
koşulunu sağladığında durur. Sayılan son yansıma, ışını açıklığa gönderen yansımadır. Verilen başlangıç ışını için toplam sayı \(354\)'tür.
C++, Python ve Java uygulamaları başlangıçta önceki nokta olarak \((0,10.1)\), mevcut nokta olarak \((1.4,-9.6)\) ve sıfırdan başlayan bir sayaç tutar. Böylece döngünün ilk turu doğrudan ilk iç çarpışmadaki yansımayı hesaplar.
Her yineleme aynı dört adımı izler: saklanan iki noktadan geliş vektörünü oluşturmak, mevcut noktadaki normali hesaplamak, yönü yansıtmak ve yukarıdaki sıfır olmayan kökle bir sonraki elips noktasına geçmek. Sonra durum bir adım ileri kaydırılır; eski mevcut nokta önceki olur, yeni bulunan nokta mevcut olur.
C++ uygulaması normali birim vektöre çevirmeden \(v-2(v\cdot n)n/(n\cdot n)\) formunu kullanır; Python ve Java ise normali önce normalize eder. Cebirsel olarak bunlar aynı doğrudur. Her güncellemeden sonra sayaç artırılır ve yeni nokta açıklık koşuluna karşı test edilir. İlk başarılı testte döngü \(354\) değerini yazar.
Işın çıkmadan önce \(B\) kez yansıyorsa süre karmaşıklığı \(O(B)\)'dir; çünkü her yinelemede sabit sayıda aritmetik işlem vardır. Bellek kullanımı \(O(1)\)'dir; yalnızca birkaç kayan nokta koordinatı, bir yön vektörü ve sayaç tutulur.
Bu problemde \(B=354\) olduğundan hesaplama çok küçüktür. Asıl önemli nokta büyük veri yapıları değil, elips üzerindeki bir sonraki çarpışmayı doğru ve kararlı biçimde hesaplayan geometrik formüldür.
El espejo es la elipse \(4x^2+y^2=100\), salvo por una abertura muy pequeña en la parte superior donde \(|x|\le 0.01\). El rayo parte de \((0,10.1)\), entra por esa abertura y su primer impacto real sobre el espejo ocurre en \((1.4,-9.6)\). Hay que contar cuántas reflexiones se producen antes de que el haz vuelva a alcanzar la abertura y salga.
El problema es un billar geométrico dentro de una elipse. Cuando ya se conocen dos puntos consecutivos de la trayectoria, el siguiente segmento queda determinado por la ley de reflexión. Por eso la derivación central consiste en describir algebraicamente un solo rebote.
Definimos \(F(x,y)=4x^2+y^2-100\). Todo punto de reflexión pertenece a la curva \(F(x,y)=0\). La idea completa es escribir un paso únicamente en función del punto anterior y del punto actual.
Un solo punto de la elipse no basta, porque el siguiente choque depende de la dirección de llegada. Si los dos últimos puntos son \(P_{k-1}\) y \(P_k\), entonces la dirección incidente en \(P_k\) es
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
Así, el estado real del sistema es el par ordenado \((P_{k-1},P_k)\). Eso es exactamente lo que guardan las implementaciones.
Para una curva implícita \(F(x,y)=0\), el gradiente es perpendicular a la curva. En este caso
$$\nabla F(x,y)=(8x,2y).$$
Por tanto, en \(P_k=(x_k,y_k)\) un vector normal es \(n=(8x_k,2y_k)\). Si \(v_{\mathrm{in}}\) es la dirección entrante, la dirección reflejada es
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
También puede usarse una normal unitaria; ambas fórmulas describen la misma recta. La interpretación geométrica es que la componente tangencial se conserva y la componente normal cambia de signo.
Desde el punto actual \(P_k=(x_k,y_k)\), el rayo reflejado se parametriza como
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
Al sustituir en la ecuación de la elipse obtenemos
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
Como \(P_k\) ya está en la elipse, el término constante desaparece y queda
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
La raíz \(t=0\) corresponde al punto actual. La otra raíz da el siguiente choque:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
Esta simplificación es importante: las implementaciones no necesitan una fórmula cuadrática general, porque el punto actual ya aporta una raíz conocida.
El haz llega desde \(P_{-1}=(0,10.1)\) hasta \(P_0=(1.4,-9.6)\), luego
$$v_{\mathrm{in}}=(1.4,-19.7).$$
En \(P_0\), la normal es
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
Aplicando la reflexión se obtiene
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
Entonces
$$t\approx 0.3275153751,$$
y el siguiente punto es
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
Ese primer valor sirve como comprobación concreta de que la implementación sigue la geometría correcta.
La parte superior no es reflectante porque ahí está la abertura. Sobre la propia elipse, la condición \(|x|\le 0.01\) con \(y>0\) identifica precisamente ese pequeño hueco. Por tanto, la simulación termina cuando el siguiente punto de impacto potencial satisface
$$|x|\le 0.01,\qquad y>0.$$
La última reflexión contada es la que envía el rayo hacia esa abertura. Para los datos del problema, el total es \(354\).
Las implementaciones en C++, Python y Java guardan el punto anterior \((0,10.1)\), el punto actual \((1.4,-9.6)\) y un contador inicializado en cero. Eso hace que la primera iteración calcule directamente la reflexión en el primer impacto interior.
En cada vuelta del bucle se realizan los mismos cuatro pasos: construir el vector incidente a partir de los dos puntos guardados, calcular la normal en el punto actual, reflejar la dirección y usar la raíz no nula anterior para saltar al siguiente punto de la elipse. Después el par de puntos se desplaza una posición hacia adelante.
La versión en C++ usa la forma no normalizada \(v-2(v\cdot n)n/(n\cdot n)\), mientras que Python y Java normalizan la normal antes. Ambas opciones son equivalentes. Tras cada actualización se incrementa el contador y se verifica la condición de salida. Cuando se cumple por primera vez, el programa imprime \(354\).
Si el haz rebota \(B\) veces antes de salir, el tiempo de ejecución es \(O(B)\), porque cada iteración hace solo un número constante de operaciones aritméticas. El uso de memoria es \(O(1)\): solo se conservan unas pocas coordenadas, un vector dirección y el contador.
En este problema concreto \(B=354\), así que el coste es mínimo. Lo relevante no es la escala computacional, sino haber obtenido una actualización geométrica exacta y estable para el siguiente punto de impacto.
镜面是椭圆 \(4x^2+y^2=100\)，只有顶部 \(|x|\le 0.01\) 的一小段被挖空，形成出入口。激光从 \((0,10.1)\) 出发，经这个开口进入椭圆内部，第一次真正打到镜面的点是 \((1.4,-9.6)\)。题目要求计算：在光线再次到达顶部开口并离开之前，一共发生了多少次反射。
这不是组合计数题，而是一个严格的几何追踪问题。只要知道轨迹上的两个相邻点，下一段路径就会被反射定律唯一决定。因此核心工作是把“一次反射后的下一个撞击点”写成显式公式。
记 \(F(x,y)=4x^2+y^2-100\)。所有反射点都满足 \(F(x,y)=0\)。整个推导围绕一个事实展开：一次更新只需要前一个点和当前点，而不需要保存整条历史轨迹。
只知道椭圆上的一个点还不够，因为下一次撞击取决于入射方向。如果最近两个点分别是 \(P_{k-1}\) 和 \(P_k\)，那么光线在 \(P_k\) 处的入射方向就是
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
所以系统的状态实际上是有序对 \((P_{k-1},P_k)\)。实现中正是保存这两个点，然后在每次循环后整体向前推进一步。
对隐式曲线 \(F(x,y)=0\) 来说，梯度向量与曲线正交。这里有
$$\nabla F(x,y)=(8x,2y).$$
因此在点 \(P_k=(x_k,y_k)\) 处，镜面的法向量可以取为 \(n=(8x_k,2y_k)\)。若入射方向为 \(v_{\mathrm{in}}\)，则反射后的方向满足
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
如果先把 \(n\) 归一化，也会得到完全等价的方向。几何意义很明确：沿切线方向的分量保持不变，沿法线方向的分量取相反数，这正是镜面反射定律。
从当前撞击点 \(P_k=(x_k,y_k)\) 出发，反射后的光线可写成
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
把它代回椭圆方程可得
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
由于 \(P_k\) 本来就在椭圆上，常数项自动消失，所以方程直接化为
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
根 \(t=0\) 对应当前点本身，另一个根才是下一次撞击：
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
这一步是整道题最重要的代数简化之一。实现并不需要调用通用二次公式，而是直接取这个非零根。
光线从 \(P_{-1}=(0,10.1)\) 到达 \(P_0=(1.4,-9.6)\)，所以
$$v_{\mathrm{in}}=(1.4,-19.7).$$
在 \(P_0\) 处，法向量为
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
代入反射公式后得到
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
再由交点公式求得
$$t\approx 0.3275153751,$$
于是下一次撞击点为
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
这个数值例子非常有用，因为它能够直接验证程序是否按照正确的几何规则更新状态。
顶部缺失的不是一个孤立点，而是一小段极短的椭圆弧。对本题的椭圆来说，只要候选撞击点满足 \(|x|\le 0.01\) 且 \(y>0\)，它就位于顶部那个开口附近，而不是反光镜面上。因此循环在下一次潜在撞击满足
$$|x|\le 0.01,\qquad y>0$$
时停止。被计数的最后一次反射，就是把光线送向开口的那一次。对于题目给定的初始光线，总反射次数为 \(354\)。
C++、Python 和 Java 实现都从同一组状态开始：前一点是 \((0,10.1)\)，当前点是 \((1.4,-9.6)\)，反射计数器初值为零。这样第一轮循环就对应第一次内部反射，而不是入射动作本身。
每次迭代都做同样的四件事：由两个已知点求入射向量，在当前点计算法向量，按反射定律得到出射方向，然后用上面的非零根一步跳到椭圆上的下一个点。之后，把状态整体前移：旧的当前点变成前一点，新求出的点变成当前点。
C++ 实现直接使用未归一化的公式 \(v-2(v\cdot n)n/(n\cdot n)\)；Python 和 Java 先把法向量归一化，再代入单位法向量形式。两种写法在代数上完全等价。每次更新后计数器加一，再检查新点是否落入顶部开口。首次满足条件时，程序输出 \(354\)。
如果光线离开前发生了 \(B\) 次反射，那么时间复杂度就是 \(O(B)\)，因为每一轮只有常数次浮点运算。空间复杂度为 \(O(1)\)：算法只保留少量坐标、一个方向向量和反射次数。
在本题中 \(B=354\)，所以实际运行量极小。真正关键的不是规模，而是几何推导是否严谨，特别是反射方向和下一次交点是否按照椭圆的法向量正确计算。
Зеркало задается эллипсом \(4x^2+y^2=100\), но в верхней части у него есть очень узкая щель, соответствующая условию \(|x|\le 0.01\). Луч стартует из точки \((0,10.1)\), входит через эту щель и впервые попадает на отражающую поверхность в точке \((1.4,-9.6)\). Нужно определить, сколько отражений произойдет до того, как луч снова попадет в верхнее отверстие и выйдет наружу.
Это геометрическая задача о трассировке луча внутри эллипса. Как только известны две соседние точки траектории, следующий участок полностью определяется законом отражения. Поэтому главная часть решения состоит в точной формуле одного шага.
Обозначим \(F(x,y)=4x^2+y^2-100\). Любая точка отражения лежит на кривой \(F(x,y)=0\). Вся схема решения выражает очередной удар только через предыдущую и текущую точки.
Одной точки на эллипсе недостаточно, потому что следующий удар зависит от направления прихода. Если последние две точки траектории равны \(P_{k-1}\) и \(P_k\), то входящий вектор в точке \(P_k\) равен
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
Значит, состояние системы задается упорядоченной парой \((P_{k-1},P_k)\). Именно эту пару и хранят реализации.
Для неявно заданной кривой \(F(x,y)=0\) градиент перпендикулярен касательной. Здесь
$$\nabla F(x,y)=(8x,2y).$$
Следовательно, в точке \(P_k=(x_k,y_k)\) нормаль можно взять в виде \(n=(8x_k,2y_k)\). Если \(v_{\mathrm{in}}\) обозначает входящее направление, то отраженный вектор равен
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
Можно предварительно нормировать \(n\); результат будет тем же. С геометрической точки зрения касательная компонента сохраняется, а нормальная меняет знак.
Из текущей точки удара \(P_k=(x_k,y_k)\) отраженный луч параметризуется так:
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
Подстановка в уравнение эллипса дает
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
Поскольку \(P_k\) уже лежит на эллипсе, свободный член исчезает, и выражение раскладывается в вид
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
Корень \(t=0\) соответствует текущей точке. Второй корень и есть следующая точка удара:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
Это важное упрощение: реализациям не нужен общий квадратный решатель, потому что один корень известен заранее.
Луч приходит из \(P_{-1}=(0,10.1)\) в \(P_0=(1.4,-9.6)\), поэтому
$$v_{\mathrm{in}}=(1.4,-19.7).$$
В точке \(P_0\) нормаль равна
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
После отражения получаем
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
Затем
$$t\approx 0.3275153751,$$
и следующая точка равна
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
Этот первый шаг полезен как численная проверка: все три реализации приходят к той же координате.
В верхней части отсутствует не одна точка, а маленький участок дуги. Для точек эллипса условие \(|x|\le 0.01\) и \(y>0\) означает попадание именно в это отверстие, а не в отражающую поверхность. Поэтому цикл останавливается, как только следующая потенциальная точка удара удовлетворяет
$$|x|\le 0.01,\qquad y>0.$$
Последним считается отражение, которое направило луч к щели. Для заданного начального луча общее число отражений равно \(354\).
Реализации на C++, Python и Java начинают с одинакового состояния: предыдущая точка \((0,10.1)\), текущая точка \((1.4,-9.6)\) и счетчик, равный нулю. Благодаря этому первая итерация уже соответствует первому внутреннему отражению.
Каждый проход цикла делает четыре геометрических шага: строит входящий вектор по двум сохраненным точкам, вычисляет нормаль в текущей точке, отражает направление и по ненулевому корню сразу находит следующую точку на эллипсе. Затем пара точек сдвигается вперед на один шаг.
Версия на C++ использует ненормированную формулу \(v-2(v\cdot n)n/(n\cdot n)\), а Python и Java сначала нормируют нормаль. Это одна и та же геометрия. После каждого шага счетчик увеличивается, а новая точка проверяется на попадание в верхнее отверстие. При первом успехе программа выводит \(354\).
Если до выхода происходит \(B\) отражений, то время работы равно \(O(B)\), потому что каждая итерация выполняет лишь постоянное число арифметических операций. Память составляет \(O(1)\): хранятся только несколько координат, один вектор направления и счетчик.
В данной задаче \(B=354\), поэтому вычисление очень мало по объему. Важна не масштабность, а то, что следующая точка удара выводится строго из геометрии эллипса и закона отражения.
المرآة هي القطع الناقص \(4x^2+y^2=100\)، لكن يوجد في أعلاه فتحة صغيرة جدًا تقابل الشرط \(|x|\le 0.01\). يبدأ الشعاع من النقطة \((0,10.1)\)، ويدخل عبر هذه الفتحة، ثم تكون أول نقطة اصطدام فعلية مع السطح العاكس عند \((1.4,-9.6)\). المطلوب هو حساب عدد الانعكاسات قبل أن يصل الشعاع مرة أخرى إلى هذه الفتحة ويغادر.
المسألة هندسية خالصة: إذا عُرفت نقطتان متتاليتان على مسار الشعاع، فإن القطعة التالية من المسار تصبح محددة تمامًا بقانون الانعكاس. لذلك فالمطلوب الحقيقي هو اشتقاق قاعدة دقيقة لانتقال واحد من اصطدام إلى الاصطدام الذي يليه.
لنعرّف \(F(x,y)=4x^2+y^2-100\). كل نقطة انعكاس تحقق المعادلة \(F(x,y)=0\). والفكرة كلها هي كتابة خطوة واحدة فقط بدلالة النقطة السابقة والنقطة الحالية.
معرفة نقطة واحدة على القطع الناقص لا تكفي، لأن الاصطدام التالي يعتمد على اتجاه الوصول. إذا كانت آخر نقطتين هما \(P_{k-1}\) و\(P_k\)، فإن متجه الدخول عند \(P_k\) هو
$$v_{\mathrm{in}}=P_k-P_{k-1}.$$
إذن حالة النظام الحقيقية هي الزوج المرتب \((P_{k-1},P_k)\). وهذا بالضبط ما تحتفظ به التطبيقات أثناء التكرار.
في المنحنى الضمني \(F(x,y)=0\)، يكون متجه التدرج عموديًا على المنحنى. وهنا لدينا
$$\nabla F(x,y)=(8x,2y).$$
لذلك عند النقطة \(P_k=(x_k,y_k)\) يمكن أخذ المتجه العمودي على السطح بالشكل \(n=(8x_k,2y_k)\). وإذا كان \(v_{\mathrm{in}}\) هو اتجاه الشعاع الداخل، فإن الاتجاه المنعكس يساوي
$$v_{\mathrm{out}}=v_{\mathrm{in}}-2\frac{v_{\mathrm{in}}\cdot n}{n\cdot n}\,n.$$
ويمكن أيضًا تطبيع \(n\) أولًا ثم استعمال صيغة المتجه العمودي الموحّد؛ النتيجة الهندسية واحدة. معنى ذلك أن المركبة المماسية تبقى كما هي، بينما تنعكس إشارة المركبة العمودية.
إذا كانت نقطة الاصطدام الحالية هي \(P_k=(x_k,y_k)\)، فإن الشعاع الخارج يُكتب على الصورة
$$P_k+t\,v_{\mathrm{out}}=(x_k+t d_x,\ y_k+t d_y).$$
بالتعويض في معادلة القطع الناقص نحصل على
$$4(x_k+t d_x)^2+(y_k+t d_y)^2=100.$$
ولأن \(P_k\) موجودة أصلًا على القطع الناقص، يختفي الحد الثابت، فتتحول المعادلة إلى
$$t\Big((4d_x^2+d_y^2)t+(8x_k d_x+2y_k d_y)\Big)=0.$$
الجذر \(t=0\) هو النقطة الحالية نفسها، أما الجذر الآخر فهو نقطة الاصطدام التالية:
$$t=-\frac{8x_k d_x+2y_k d_y}{4d_x^2+d_y^2}.$$
هذه هي الخطوة الجبرية الحاسمة في الحل؛ فلا حاجة إلى استعمال الصيغة العامة للمعادلة التربيعية، لأن أحد الجذرين معروف مسبقًا.
يصل الشعاع من \(P_{-1}=(0,10.1)\) إلى \(P_0=(1.4,-9.6)\)، ولذلك
$$v_{\mathrm{in}}=(1.4,-19.7).$$
وعند \(P_0\) يكون المتجه العمودي
$$n=(8\cdot 1.4,\ 2\cdot (-9.6))=(11.2,-19.2).$$
وبتطبيق قانون الانعكاس نحصل على
$$v_{\mathrm{out}}\approx(-16.4590673575,\ 10.9155440415).$$
ثم نجد
$$t\approx 0.3275153751,$$
ومن ثم تكون النقطة التالية
$$P_1=P_0+t\,v_{\mathrm{out}}\approx(-3.9905976194,\ -6.0249914989).$$
هذا المثال العددي مهم لأنه يعطي نقطة فحص مباشرة للتأكد من أن التنفيذ يتبع الهندسة الصحيحة.
الفتحة في أعلى المرآة ليست نقطة منفردة بل قطعة قصيرة جدًا من القوس العلوي. وعلى هذا القطع الناقص، فإن تحقق الشرطين \(|x|\le 0.01\) و\(y>0\) يعني أن نقطة الاصطدام المحتملة تقع في منطقة الفتحة لا على السطح العاكس. لذلك تتوقف المحاكاة عندما تحقق النقطة التالية الشرط
$$|x|\le 0.01,\qquad y>0.$$
آخر انعكاس يُحسب هو الانعكاس الذي يوجّه الشعاع نحو هذه الفتحة. وبالنسبة للشعاع الابتدائي المعطى، يكون العدد الكلي للانعكاسات \(354\).
تبدأ تطبيقات C++ وPython وJava بالحالة نفسها: النقطة السابقة \((0,10.1)\)، والنقطة الحالية \((1.4,-9.6)\)، وعدّاد انعكاسات يساوي صفرًا. وهذا يعني أن أول دورة في الحلقة تتعامل مباشرة مع أول انعكاس داخل المرآة.
كل تكرار ينفذ الخطوات الهندسية نفسها: تكوين متجه الدخول من النقطتين المخزنتين، حساب المتجه العمودي عند النقطة الحالية، عكس الاتجاه، ثم استعمال الجذر غير الصفري للانتقال مباشرة إلى النقطة التالية على القطع الناقص. بعد ذلك تُحرَّك الحالة خطوة إلى الأمام.
تنفيذ C++ يستعمل الصيغة غير المطبّعة \(v-2(v\cdot n)n/(n\cdot n)\)، بينما يقوم Python وJava بتطبيع المتجه العمودي أولًا. الصيغتان متكافئتان جبريًا. بعد كل تحديث يزداد العدّاد بمقدار واحد، ثم تُفحَص النقطة الجديدة لمعرفة هل وصلت إلى الفتحة. عند أول تحقق، يطبع البرنامج القيمة \(354\).
إذا حدث \(B\) انعكاسات قبل الخروج، فإن زمن التنفيذ يساوي \(O(B)\)، لأن كل دورة تستخدم عددًا ثابتًا من العمليات الحسابية. أما الذاكرة فهي \(O(1)\)، إذ لا حاجة إلا إلى بضع إحداثيات ومتجه اتجاه وعدّاد.
في هذه المسألة تحديدًا \(B=354\)، لذا فالحساب صغير جدًا. النقطة الأساسية ليست حجم العمل الحسابي، بل أن تكون صيغة الاتجاه المنعكس ونقطة التقاطع التالية مشتقة بدقة من هندسة القطع الناقص.