We generate \(k\) deterministic points in the plane from the recurrence
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
and, using zero-based indexing, define
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
The goal is to find the minimum Euclidean distance between any two generated points. For \(k=2{,}000{,}000\), a naive \(O(k^2)\) scan over all pairs is completely infeasible, so the solution uses closest-pair geometry to discard almost all comparisons.
Write each point as \(P_i=(x_i,y_i)\). The target quantity is
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
The key observation is that closest-pair algorithms do not need to compare every pair. Geometry lets us keep only a narrow set of candidates near the current point or near the current dividing line.
The recurrence is deterministic, so the entire input is fixed once \(k\) is given. The first few points are
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
Nothing random remains after generation; the computational problem is purely geometric.
Because the square-root function is strictly increasing, minimizing the Euclidean distance is equivalent to minimizing its square. Define
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
Then
$$\delta_k=\sqrt{\Delta_k}.$$
This matters in the implementation because squared distances stay integral and can be compared exactly. The square root is needed only when a geometric width \(d=\sqrt{\Delta}\) is required, or when the final answer is printed.
After sorting the points by increasing \(x\)-coordinate, suppose the current best squared distance is \(\Delta\), and let \(d=\sqrt{\Delta}\).
Consider a current point \(P_i\) and an earlier point \(P_j\). If
$$x_i-x_j>d,$$
then automatically
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta,$$
so that pair cannot improve the answer. Therefore only points lying within a vertical strip of width \(d\) behind the current point can still matter.
Even inside that vertical strip, most points can still be ignored. If
$$|y_i-y_j|>d,$$
then
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
so the pair is again impossible. Hence only points with
$$y_j\in[y_i-d,\ y_i+d]$$
need to be checked. This is why the active candidates are maintained in \(y\)-order, or why the central strip is sorted by \(y\) in the divide-and-conquer formulation.
There is an equivalent classical view. Split the \(x\)-sorted array into left and right halves, solve each half recursively, and let
$$\Delta=\min(\Delta_L,\Delta_R).$$
Any pair that beats \(\Delta\) but lies across the split must satisfy
$$|x-m|<d,$$
where \(m\) is the \(x\)-coordinate of the dividing line, so both points lie inside a central strip of width \(2d\). Once that strip is ordered by \(y\), it is enough to compare each point only with later strip points until the \(y\)-gap alone already forces the squared distance to be at least \(\Delta\). This is the standard closest-pair theorem.
For the first \(14\) generated points, the closest pair is
$$ (18885138,9652189),\qquad(19047286,9130354). $$
The coordinate differences are
$$\Delta x=162148,\qquad \Delta y=-521835,$$
so the squared distance is
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
Therefore
$$d(14)=\sqrt{298603741129}\approx 546446.466846479,$$
which is the checkpoint reproduced by the implementations.
The C++, Python, and Java implementations all begin the same way: generate the deterministic points, sort them by \(x\), and store the current best value as a squared distance in integer arithmetic.
The C++ and Python implementations use a sweep line. As the scan moves from left to right, points whose \(x\)-distance from the current point already exceeds the current best distance are removed from the active structure. The remaining active points are ordered by \(y\), so the implementation inspects only the narrow \(y\)-window that can still improve the answer.
The Java implementation uses divide and conquer. It solves the left and right halves recursively, keeps the smaller squared distance, then builds the central strip near the median \(x\)-coordinate. That strip is sorted by \(y\), and comparisons stop as soon as the \(y\)-difference alone is too large.
In all three implementations, the final step is a single square root followed by formatting to nine decimal places.
Point generation costs \(O(k)\) time and \(O(k)\) memory. Sorting costs \(O(k\log k)\). The Java divide-and-conquer implementation has the standard \(O(k\log k)\) running time with \(O(k)\) auxiliary memory. The C++ and Python sweep-line implementations also use \(O(k)\) memory and are designed to remain close to \(O(k\log k)\) on this data, because each point enters and leaves the active set once and only a narrow candidate strip is searched for each new point.
Es werden \(k\) deterministische Punkte in der Ebene durch die Rekursion
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
erzeugt; bei nullbasierter Indizierung gilt
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
Gesucht ist der kleinste euklidische Abstand zwischen zwei erzeugten Punkten. Für \(k=2{,}000{,}000\) ist ein vollständiger \(O(k^2)\)-Vergleich unmöglich, daher nutzt die Lösung die Geometrie des Closest-Pair-Problems.
Schreibe \(P_i=(x_i,y_i)\). Die Zielgröße ist
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
Die zentrale Beobachtung ist, dass man nicht alle Punktpaare vergleichen muss. Durch geometrische Schranken bleiben nur sehr wenige Kandidaten in der Nähe des aktuellen Punkts oder der Trennlinie übrig.
Die Rekursion ist vollständig deterministisch; für gegebenes \(k\) steht also die gesamte Eingabe fest. Die ersten Punkte sind
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
Nach der Erzeugung bleibt nur noch ein geometrisches Problem: Finde das nächste Punktpaar.
Da die Quadratwurzel streng monoton wächst, genügt es, das Quadrat der Distanz zu minimieren. Definiere
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
Dann gilt
$$\delta_k=\sqrt{\Delta_k}.$$
Das ist wichtig für die Implementierung: quadrierte Distanzen bleiben ganze Zahlen und lassen sich exakt vergleichen. Die Quadratwurzel wird erst für die Fensterbreite \(d=\sqrt{\Delta}\) oder für die Endausgabe benötigt.
Sortiere die Punkte nach steigender \(x\)-Koordinate. Sei \(\Delta\) die aktuell beste quadrierte Distanz und \(d=\sqrt{\Delta}\).
Für einen aktuellen Punkt \(P_i\) und einen früheren Punkt \(P_j\) gilt: Falls
$$x_i-x_j>d,$$
dann automatisch
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta,$$
also kann dieses Paar den Bestwert nicht verbessern. Relevant bleiben nur Punkte in einem vertikalen Streifen der Breite \(d\) hinter dem aktuellen Punkt.
Auch innerhalb dieses Streifens sind die meisten Punkte unnötig. Wenn
$$|y_i-y_j|>d,$$
dann folgt
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
also ist auch dieses Paar ausgeschlossen. Es genügt daher, nur Punkte mit
$$y_j\in[y_i-d,\ y_i+d]$$
zu betrachten. Genau deshalb werden die aktiven Kandidaten nach \(y\) geordnet gehalten, beziehungsweise der Mittelstreifen im Divide-and-Conquer-Verfahren nach \(y\) sortiert.
Man kann dieselbe Idee auch rekursiv formulieren. Teile das nach \(x\) sortierte Feld in eine linke und eine rechte Hälfte und berechne rekursiv
$$\Delta=\min(\Delta_L,\Delta_R).$$
Ein Paar aus verschiedenen Hälften kann \(\Delta\) nur schlagen, wenn beide Punkte
$$|x-m|<d$$
erfüllen, wobei \(m\) die \(x\)-Koordinate der Mittellinie ist, also in einem zentralen Streifen der Breite \(2d\) liegen. Wird dieser Streifen nach \(y\) sortiert, dann reicht es, für jeden Punkt nur so lange nach oben zu prüfen, bis bereits der \(y\)-Abstand allein die Schranke \(\Delta\) erzwingt.
Für die ersten \(14\) erzeugten Punkte ist das nächste Paar
$$ (18885138,9652189),\qquad(19047286,9130354). $$
Die Koordinatendifferenzen sind
$$\Delta x=162148,\qquad \Delta y=-521835,$$
also beträgt die quadrierte Distanz
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
Daraus folgt
$$d(14)=\sqrt{298603741129}\approx 546446.466846479,$$
genau der Kontrollwert, den die Implementierungen reproduzieren.
Die C++-, Python- und Java-Implementierungen beginnen alle gleich: Sie erzeugen die deterministischen Punkte, sortieren sie nach \(x\) und halten den aktuellen Bestwert als quadrierte Distanz in Ganzzahlarithmetik fest.
Die C++- und Python-Implementierungen verwenden dann eine Sweep-Line. Während der Scan nach rechts läuft, werden Punkte entfernt, deren \(x\)-Abstand zum aktuellen Punkt bereits größer als die aktuelle Bestdistanz ist. Die übrigen aktiven Punkte sind nach \(y\) geordnet, sodass nur das schmale \(y\)-Fenster geprüft werden muss.
Die Java-Implementierung verwendet Divide and Conquer. Sie löst linke und rechte Hälfte rekursiv, übernimmt die kleinere quadrierte Distanz und untersucht danach nur den mittleren Streifen in der Nähe der Trennlinie. Dieser Streifen wird nach \(y\) sortiert, und die Vergleiche enden, sobald der \(y\)-Abstand allein schon zu groß ist.
Am Ende wird genau eine Quadratwurzel gezogen und das Ergebnis mit neun Nachkommastellen ausgegeben.
Die Punkterzeugung kostet \(O(k)\) Zeit und \(O(k)\) Speicher. Das Sortieren kostet \(O(k\log k)\). Die Java-Implementierung mit Divide and Conquer erreicht die klassische Laufzeit \(O(k\log k)\) bei \(O(k)\) Zusatzspeicher. Die Sweep-Line-Implementierungen in C++ und Python benötigen ebenfalls \(O(k)\) Speicher und sind für diese Daten so aufgebaut, dass sie nahe bei \(O(k\log k)\) bleiben, weil jeder Punkt genau einmal in die aktive Struktur eintritt und sie wieder verlässt und pro Schritt nur ein schmales Kandidatenfenster untersucht wird.
Düzlemdeki \(k\) adet deterministik nokta şu bağıntıyla üretilir:
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797.$$
Sıfır tabanlı indisleme kullanılırsa noktalar
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k$$
şeklindedir. Amaç, üretilen herhangi iki nokta arasındaki en küçük Öklid uzaklığını bulmaktır. \(k=2{,}000{,}000\) için tüm çiftleri \(O(k^2)\) ile denemek pratik değildir; bu yüzden çözüm, en yakın nokta çifti geometrisini kullanarak karşılaştırmaların büyük kısmını eler.
Her noktayı \(P_i=(x_i,y_i)\) diye yazalım. Aranan büyüklük
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$
olur. Temel fikir, tüm nokta çiftlerini kontrol etmek zorunda olmamamızdır. Geometrik sınırlar, sadece mevcut noktaya ya da ayırıcı doğruya yakın çok dar bir aday kümesinin önemli olduğunu söyler.
Bağıntı tamamen deterministiktir; dolayısıyla \(k\) verildiğinde girişin tamamı da sabittir. İlk birkaç nokta şöyledir:
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
Noktalar üretildikten sonra problem artık tamamen geometriktir: en yakın çifti bulmak gerekir.
Karekök fonksiyonu sıkı artan olduğundan, Öklid uzaklığını minimize etmek ile uzaklığın karesini minimize etmek aynı şeydir. Şunu tanımlayalım:
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
Böylece
$$\delta_k=\sqrt{\Delta_k}$$
olur. Bu dönüşüm uygulamada çok önemlidir; çünkü kare uzaklıklar tam sayı olarak tutulabilir ve hatasız karşılaştırılabilir. Karekök sadece pencere genişliği \(d=\sqrt{\Delta}\) gerektiğinde ya da sonuç yazdırılırken alınır.
Noktaları artan \(x\) değerine göre sıralayalım. Mevcut en iyi kare uzaklık \(\Delta\) ve buna karşılık gelen uzaklık \(d=\sqrt{\Delta}\) olsun.
Güncel nokta \(P_i\) ile daha eski bir nokta \(P_j\) için eğer
$$x_i-x_j>d,$$
ise otomatik olarak
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta$$
olur. Yani bu çift artık cevabı iyileştiremez. Demek ki yalnızca güncel noktanın gerisinde, genişliği \(d\) olan dikey bir şerit içinde kalan noktalar adaydır.
Bu dikey şerit içinde bile çoğu nokta gereksizdir. Eğer
$$|y_i-y_j|>d,$$
ise
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta$$
olur ve çift yine elenir. O halde yalnızca
$$y_j\in[y_i-d,\ y_i+d]$$
aralığındaki noktaların kontrol edilmesi yeterlidir. Aktif adayların \(y\)'ye göre sıralı tutulmasının ya da böl-ve-yönet yönteminde orta şeridin \(y\)'ye göre sıralanmasının nedeni tam olarak budur.
Aynı fikir rekürsif biçimde de yazılabilir. \(x\)'e göre sıralı diziyi sol ve sağ yarıya ayırıp her yarı için çözüm bulunur ve
$$\Delta=\min(\Delta_L,\Delta_R)$$
alınır. Bu değeri geçen fakat iki farklı yarıda bulunan bir çift varsa, her iki nokta da
$$|x-m|<d$$
koşulunu sağlamalıdır; burada \(m\) orta çizginin \(x\) koordinatıdır. Yani ikisi de genişliği \(2d\) olan merkezi şeritte bulunur. Bu şerit \(y\)'ye göre sıralandığında, her nokta için yalnızca \(y\) farkı küçük kaldığı sürece yukarıdaki adaylar karşılaştırılır.
İlk \(14\) üretilen nokta içinde en yakın çift şudur:
$$ (18885138,9652189),\qquad(19047286,9130354). $$
Koordinat farkları
$$\Delta x=162148,\qquad \Delta y=-521835$$
olduğu için kare uzaklık
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129$$
çıkar. Dolayısıyla
$$d(14)=\sqrt{298603741129}\approx 546446.466846479$$
elde edilir; bu değer uygulamaların kullandığı kontrol sonucudur.
C++, Python ve Java implementasyonlarının ortak başlangıcı aynıdır: deterministik noktalar üretilir, noktalar \(x\)'e göre sıralanır ve mevcut en iyi değer tam sayı kare uzaklık olarak tutulur.
C++ ve Python implementasyonları sweep-line yaklaşımını kullanır. Tarama soldan sağa ilerlerken, güncel noktaya \(x\) bakımından artık fazla uzakta kalan noktalar aktif yapıdan çıkarılır. Geriye kalan aktif noktalar \(y\)'ye göre sıralıdır; bu yüzden yalnızca dar \(y\)-penceresindeki adaylar karşılaştırılır.
Java implementasyonu ise böl ve yönet yaklaşımını kullanır. Sol ve sağ yarılar rekürsif çözülür, daha küçük kare uzaklık tutulur, sonra yalnızca orta çizgiye yakın merkezi şerit incelenir. Bu şerit \(y\)'ye göre sıralanır ve \(y\) farkı tek başına yeterince büyüdüğünde karşılaştırma durdurulur.
Üç implementasyonda da son adım bir kez karekök almak ve sonucu dokuz basamakla biçimlendirmektir.
Nokta üretimi \(O(k)\) zaman ve \(O(k)\) bellek gerektirir. Sıralama \(O(k\log k)\) sürer. Java’daki böl ve yönet implementasyonu klasik \(O(k\log k)\) zaman ve \(O(k)\) ek bellek sınırını sağlar. C++ ve Python’daki sweep-line implementasyonları da \(O(k)\) bellek kullanır ve bu veri üzerinde \(O(k\log k)\) civarında kalacak şekilde tasarlanmıştır; çünkü her nokta aktif yapıya bir kez girer, bir kez çıkar ve her adımda yalnızca dar bir aday şeridi taranır.
Se generan \(k\) puntos deterministas en el plano mediante la recurrencia
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
y, usando índices desde \(0\), se define
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
La tarea consiste en hallar la menor distancia euclídea entre dos puntos generados. Para \(k=2{,}000{,}000\), revisar todos los pares en \(O(k^2)\) es inviable, así que la solución usa la geometría clásica del problema del par más cercano.
Escribamos \(P_i=(x_i,y_i)\). La cantidad buscada es
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
La idea principal es que no hace falta comparar todos los pares. Las restricciones geométricas permiten conservar solo una franja estrecha de candidatos cerca del punto actual o de la línea divisoria.
La recurrencia es completamente determinista; una vez fijado \(k\), toda la entrada queda determinada. Los primeros puntos son
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
Después de esta fase, el problema ya es puramente geométrico.
Como la raíz cuadrada es estrictamente creciente, minimizar la distancia euclídea equivale a minimizar su cuadrado. Definimos
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
Entonces
$$\delta_k=\sqrt{\Delta_k}.$$
Esto es importante en la implementación porque las distancias cuadradas permanecen enteras y se comparan sin error. La raíz cuadrada solo se usa para obtener el ancho geométrico \(d=\sqrt{\Delta}\) o para imprimir la respuesta final.
Tras ordenar los puntos por coordenada \(x\), supongamos que la mejor distancia cuadrada actual es \(\Delta\), y definamos \(d=\sqrt{\Delta}\).
Si para el punto actual \(P_i\) y un punto anterior \(P_j\) se cumple
$$x_i-x_j>d,$$
entonces automáticamente
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta,$$
de modo que ese par no puede mejorar la solución. Por tanto, solo importan los puntos situados dentro de una franja vertical de ancho \(d\) detrás del punto actual.
Incluso dentro de esa franja vertical, la mayoría de los puntos siguen siendo inútiles. Si
$$|y_i-y_j|>d,$$
entonces
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
así que ese par también queda descartado. Basta revisar los puntos con
$$y_j\in[y_i-d,\ y_i+d].$$
Por eso los candidatos activos se mantienen ordenados por \(y\), o bien la franja central se ordena por \(y\) en la formulación por divide y vencerás.
Existe una formulación equivalente y clásica. Se divide el arreglo ordenado por \(x\) en mitades izquierda y derecha, se resuelve cada mitad de forma recursiva y se toma
$$\Delta=\min(\Delta_L,\Delta_R).$$
Cualquier par que mejore \(\Delta\) y cruce la partición debe satisfacer
$$|x-m|<d,$$
donde \(m\) es la coordenada \(x\) de la línea media, así que ambos puntos quedan dentro de una franja central de ancho \(2d\). Si esa franja se ordena por \(y\), para cada punto solo es necesario avanzar mientras la diferencia en \(y\) siga siendo suficientemente pequeña.
Entre los primeros \(14\) puntos generados, el par más cercano es
$$ (18885138,9652189),\qquad(19047286,9130354). $$
Las diferencias de coordenadas son
$$\Delta x=162148,\qquad \Delta y=-521835,$$
por lo que la distancia cuadrada vale
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
Así,
$$d(14)=\sqrt{298603741129}\approx 546446.466846479,$$
que es exactamente el valor de comprobación reproducido por las implementaciones.
Las implementaciones en C++, Python y Java empiezan de la misma manera: generan los puntos deterministas, los ordenan por \(x\) y guardan el mejor valor actual como distancia cuadrada entera.
Las implementaciones en C++ y Python usan una línea de barrido. A medida que el recorrido avanza hacia la derecha, se eliminan los puntos cuya separación en \(x\) respecto al punto actual ya supera la mejor distancia conocida. Los puntos restantes se conservan ordenados por \(y\), así que solo se revisa la estrecha ventana en \(y\) que todavía puede mejorar la respuesta.
La implementación en Java usa divide y vencerás. Resuelve recursivamente la mitad izquierda y la mitad derecha, conserva la menor distancia cuadrada y luego inspecciona solo la franja central cercana a la mediana en \(x\). Esa franja se ordena por \(y\), y las comparaciones se detienen cuando la diferencia en \(y\) por sí sola ya es demasiado grande.
En los tres casos, el último paso es aplicar una sola raíz cuadrada y formatear el resultado con nueve decimales.
Generar los puntos cuesta \(O(k)\) tiempo y \(O(k)\) memoria. Ordenarlos cuesta \(O(k\log k)\). La implementación en Java basada en divide y vencerás alcanza la cota clásica \(O(k\log k)\) con \(O(k)\) memoria auxiliar. Las implementaciones de C++ y Python basadas en barrido también usan \(O(k)\) memoria y están diseñadas para mantenerse cerca de \(O(k\log k)\) en estos datos, porque cada punto entra y sale una sola vez de la estructura activa y en cada paso solo se examina una franja muy estrecha de candidatos.
题目先通过递推式生成平面上的 \(k\) 个确定性点：
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797.$$
如果采用从 \(0\) 开始的编号，则点为
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
目标是求这些点中任意两点之间的最小欧几里得距离。对于 \(k=2{,}000{,}000\)，如果直接枚举所有点对，需要 \(O(k^2)\) 次比较，完全不可行，因此必须利用最近点对问题的几何结构，把绝大多数无关的比较提前剪掉。
把每个点写成 \(P_i=(x_i,y_i)\)。要求的量是
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
核心思想是：最短距离不需要通过“所有点对都比较一遍”来得到。只要按合适的顺序组织点集，就能证明真正有可能成为最优解的候选点只出现在一条很窄的区域中。
这个递推并不是运行时随机抽样，而是完全确定的序列；一旦 \(k\) 固定，整个输入集合也就固定。前几个点是
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
因此，问题的难点不在点的生成，而在于如何高效地找出最近的那一对点。
由于平方根函数严格单调递增，所以最小化欧几里得距离与最小化它的平方完全等价。定义
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
那么就有
$$\delta_k=\sqrt{\Delta_k}.$$
这一点在实现里非常重要，因为平方距离始终是整数，可以精确比较，不会引入浮点误差。只有当需要得到当前几何窗口的宽度 \(d=\sqrt{\Delta}\) 或者输出最终结果时，才真正开平方。
先把所有点按 \(x\) 坐标递增排序。设当前已知的最好平方距离为 \(\Delta\)，并记
$$d=\sqrt{\Delta}.$$
现在看当前点 \(P_i\) 与一个更早的点 \(P_j\)。如果
$$x_i-x_j>d,$$
那么必然有
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta.$$
这说明该点对不可能改写最优答案。于是，对当前点来说，只需要关心那些在 \(x\) 方向上与它相距不超过 \(d\) 的旧点。换句话说，真正需要保留的候选点只落在当前点左侧一个宽度为 \(d\) 的狭窄竖条里。
即使已经限制在上面的竖条中，候选点仍然可能不少，但还可以继续缩小。若某个旧点满足
$$|y_i-y_j|>d,$$
则有
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
它同样不可能优于当前最好值。于是，当前点只需要和那些满足
$$y_j\in[y_i-d,\ y_i+d]$$
的点比较即可。这就是为什么扫描线版本要把活跃候选点按 \(y\) 排序，而分治版本则要把中间条带按 \(y\) 排序。
除了扫描线，还可以用经典的分治视角理解同一个问题。把按 \(x\) 排序后的点集分成左右两半，分别求出两边内部的最优平方距离，然后取
$$\Delta=\min(\Delta_L,\Delta_R).$$
如果真正更优的点对跨越了这条分界线，那么两点都必须满足
$$|x-m|<d,$$
其中 \(m\) 表示分界线的 \(x\) 坐标，也就是都落在宽度为 \(2d\) 的中央条带内。只要把这条带中的点再按 \(y\) 排序，就可以从下往上扫描；对每个点，只需要继续比较到“仅仅 \(y\) 方向的差距就已经不可能更优”为止。这正是最近点对问题的经典定理。
对于前 \(14\) 个生成点，最近的一对是
$$ (18885138,9652189),\qquad(19047286,9130354). $$
它们的坐标差为
$$\Delta x=162148,\qquad \Delta y=-521835,$$
因此平方距离等于
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
于是
$$d(14)=\sqrt{298603741129}\approx 546446.466846479.$$
这个数值正好是实现中使用的已知校验结果，说明数学推导和程序行为是一致的。
C++、Python 和 Java 三个实现的共同起点都是：先生成全部确定性点，再按 \(x\) 坐标排序，并且始终用整数平方距离保存当前最优值。
C++ 和 Python 实现采用扫描线思路。扫描从左向右推进时，那些在 \(x\) 方向上已经比当前最优距离还要远的旧点会被移出活跃集合。剩余活跃点按 \(y\) 坐标组织，因此当前点只需要和落在窄 \(y\) 窗口中的少量候选点比较。
Java 实现采用分治法。它递归求解左半部分和右半部分，保留较小的平方距离，然后只构造靠近中位 \(x\) 坐标的中央条带。该条带按 \(y\) 排序后，从每个点向后检查；一旦仅凭 \(y\) 的差值就足以保证不可能更优，比较就立即停止。
三种实现最后都只做一次平方根运算，并把答案格式化为九位小数。
生成点需要 \(O(k)\) 时间和 \(O(k)\) 空间，排序需要 \(O(k\log k)\)。Java 的分治实现达到教科书级别的 \(O(k\log k)\) 时间复杂度，并使用 \(O(k)\) 额外空间。C++ 和 Python 的扫描线实现同样使用 \(O(k)\) 空间，并且在这组数据上设计为接近 \(O(k\log k)\) 的行为，因为每个点只会进入和离开活跃结构一次，而且每一步只会检查很窄的候选条带。
Нужно сгенерировать \(k\) детерминированных точек на плоскости по рекуррентной формуле
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
а затем, при нумерации с нуля, взять точки
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
Требуется найти минимальное евклидово расстояние между двумя сгенерированными точками. При \(k=2{,}000{,}000\) полный перебор всех пар за \(O(k^2)\) невозможен, поэтому решение опирается на геометрию задачи о ближайшей паре точек.
Обозначим \(P_i=(x_i,y_i)\). Искомая величина равна
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
Ключевая идея состоит в том, что проверять каждую пару не нужно. Геометрические оценки позволяют оставить только узкое множество кандидатов возле текущей точки или около разделяющей линии.
Последовательность полностью фиксирована после выбора \(k\), поэтому входные данные заранее определены. Первые точки таковы:
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
После генерации остается чисто вычислительная геометрия: найти ближайшую пару.
Поскольку функция квадратного корня строго возрастает, минимизация обычного расстояния эквивалентна минимизации его квадрата. Введем
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
Тогда
$$\delta_k=\sqrt{\Delta_k}.$$
Это важно для кода: квадраты расстояний остаются целыми числами и сравниваются точно. Квадратный корень нужен только при вычислении текущей геометрической ширины \(d=\sqrt{\Delta}\) или при выводе окончательного ответа.
После сортировки точек по \(x\) пусть текущий лучший квадрат расстояния равен \(\Delta\), а \(d=\sqrt{\Delta}\).
Если для текущей точки \(P_i\) и более ранней точки \(P_j\) выполняется
$$x_i-x_j>d,$$
то сразу получаем
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta,$$
и такая пара уже не может улучшить ответ. Значит, нужно хранить только точки, лежащие в вертикальной полосе ширины \(d\) позади текущей точки.
Даже внутри этой вертикальной полосы большая часть точек не нужна. Если
$$|y_i-y_j|>d,$$
то
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
поэтому такая пара тоже бесполезна. Остается проверять только точки, удовлетворяющие
$$y_j\in[y_i-d,\ y_i+d].$$
Именно поэтому активные кандидаты поддерживаются упорядоченными по \(y\), а в варианте divide and conquer центральная полоса сортируется по \(y\).
Тот же принцип можно записать рекурсивно. Разобьем массив, отсортированный по \(x\), на левую и правую половины, решим каждую половину отдельно и возьмем
$$\Delta=\min(\Delta_L,\Delta_R).$$
Любая лучшая пара, пересекающая границу разбиения, должна удовлетворять условию
$$|x-m|<d,$$
где \(m\) обозначает \(x\)-координату линии разбиения, то есть обе точки обязаны лежать в центральной полосе ширины \(2d\). Если эту полосу отсортировать по \(y\), то для каждой точки достаточно сравнивать ее только с последующими точками, пока разность по \(y\) сама по себе еще не исключает улучшение.
Для первых \(14\) сгенерированных точек ближайшая пара такова:
$$ (18885138,9652189),\qquad(19047286,9130354). $$
Разности координат равны
$$\Delta x=162148,\qquad \Delta y=-521835,$$
поэтому квадрат расстояния равен
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
Следовательно,
$$d(14)=\sqrt{298603741129}\approx 546446.466846479,$$
и именно это контрольное значение воспроизводят реализации.
Реализации на C++, Python и Java начинают одинаково: генерируют все точки, сортируют их по \(x\) и хранят текущий лучший результат как квадрат расстояния в целочисленной арифметике.
Реализации на C++ и Python используют sweep-line. По мере движения слева направо из активной структуры удаляются точки, которые уже слишком далеки по \(x\) от текущей точки. Оставшиеся точки упорядочены по \(y\), поэтому проверяется только узкое окно по \(y\), которое еще может улучшить ответ.
Реализация на Java использует divide and conquer. Она рекурсивно решает левую и правую половины, сохраняет меньший квадрат расстояния, а затем рассматривает только центральную полосу возле медианы по \(x\). Эта полоса сортируется по \(y\), и перебор прекращается, как только одной лишь разности по \(y\) уже достаточно, чтобы исключить улучшение.
Во всех трех реализациях в конце выполняется одна операция извлечения квадратного корня и форматирование ответа с точностью до девяти знаков после запятой.
Генерация точек требует \(O(k)\) времени и \(O(k)\) памяти. Сортировка требует \(O(k\log k)\). Реализация на Java с divide and conquer дает стандартную асимптотику \(O(k\log k)\) по времени и \(O(k)\) по дополнительной памяти. Реализации на C++ и Python со sweep-line также используют \(O(k)\) памяти и рассчитаны на поведение, близкое к \(O(k\log k)\) на этих данных, поскольку каждая точка добавляется в активную структуру и удаляется из нее ровно один раз, а на каждом шаге просматривается только узкая полоса кандидатов.
نولّد \(k\) نقطة حتمية في المستوى من خلال العلاقة
$$s_{n+1}=s_n^2 \bmod 50515093,\qquad s_0=290797,$$
ومع استخدام فهرسة تبدأ من الصفر تكون النقاط
$$P_i=(s_{2i},s_{2i+1}),\qquad 0\le i<k.$$
المطلوب هو إيجاد أصغر مسافة إقليدية بين أي نقطتين من هذه النقاط. عندما يكون \(k=2{,}000{,}000\)، فإن فحص جميع الأزواج بتعقيد \(O(k^2)\) غير عملي إطلاقًا، لذلك تعتمد الفكرة على هندسة مسألة أقرب زوج نقاط لاستبعاد معظم المقارنات مسبقًا.
لنكتب كل نقطة على الصورة \(P_i=(x_i,y_i)\). الكمية المطلوبة هي
$$\delta_k=\min_{0\le i<j<k}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.$$
الفكرة الأساسية هي أننا لا نحتاج إلى مقارنة كل زوج ممكن. القيود الهندسية تضمن أن الأزواج القادرة فعلًا على تحسين الجواب تقع داخل نطاق ضيق جدًا حول النقطة الحالية أو حول خط الفصل في صياغة القسمة والتغلب.
هذه المتتالية ليست عشوائية أثناء التنفيذ؛ بل هي محددة بالكامل بمجرد اختيار \(k\). أولى النقاط هي
$$\begin{aligned} P_0&=(290797,629527),\\ P_1&=(13339144,15552512),\\ P_2&=(17939732,3034546),\\ P_3&=(22608053,23794117). \end{aligned}$$
بعد هذه المرحلة يصبح التحدي هندسيًا بحتًا: كيف نحدد أقرب زوج نقاط بكفاءة؟
بما أن دالة الجذر التربيعي تزايدية تمامًا، فإن تصغير المسافة الإقليدية يكافئ تصغير مربعها. نعرّف
$$\Delta_k=\min_{0\le i<j<k}\left((x_i-x_j)^2+(y_i-y_j)^2\right).$$
وعندئذ
$$\delta_k=\sqrt{\Delta_k}.$$
لهذا التحويل قيمة عملية واضحة: مربعات المسافات تبقى أعدادًا صحيحة ويمكن مقارنتها بدقة تامة. لا نحتاج إلى أخذ الجذر إلا عند استخراج عرض النافذة الهندسية \(d=\sqrt{\Delta}\) أو عند طباعة الجواب النهائي.
بعد ترتيب النقاط تصاعديًا حسب الإحداثي \(x\)، لنفترض أن أفضل مربع مسافة حالي هو \(\Delta\)، ولتكن
$$d=\sqrt{\Delta}.$$
إذا كانت لدينا النقطة الحالية \(P_i\) ونقطة أقدم \(P_j\) بحيث
$$x_i-x_j>d,$$
فإننا نحصل مباشرة على
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (x_i-x_j)^2 > d^2=\Delta,$$
ومن ثم لا يمكن لهذا الزوج أن يحسن الجواب. لذلك لا نحتاج إلا إلى النقاط الموجودة داخل شريط رأسي عرضه \(d\) خلف النقطة الحالية.
حتى داخل ذلك الشريط الرأسي ما زال معظم المرشحين غير مفيدين. فإذا تحقق
$$|y_i-y_j|>d,$$
فإن
$$ (x_i-x_j)^2+(y_i-y_j)^2 \ge (y_i-y_j)^2 > d^2=\Delta,$$
وبالتالي يُستبعد الزوج أيضًا. إذن يكفي فحص النقاط التي تحقق
$$y_j\in[y_i-d,\ y_i+d].$$
ولهذا السبب تُرتَّب النقاط النشطة حسب \(y\) في طريقة sweep-line، أو يُرتَّب الشريط المركزي حسب \(y\) في طريقة القسمة والتغلب.
يمكن صياغة الفكرة نفسها أيضًا بصورة تراجعية عبر القسمة والتغلب. نقسم المصفوفة المرتبة حسب \(x\) إلى نصفين، ونحسب الحل في كل نصف، ثم نأخذ
$$\Delta=\min(\Delta_L,\Delta_R).$$
وأي زوج يعبر خط القسمة ويستطيع تحسين \(\Delta\) لا بد أن يحقق
$$|x-m|<d,$$
حيث تمثل \(m\) إحداثي \(x\) لخط الوسط. أي إن النقطتين تقعان داخل شريط مركزي عرضه \(2d\). وإذا رُتّبت نقاط هذا الشريط حسب \(y\)، فلكل نقطة نتابع المقارنة فقط ما دام فرق \(y\) وحده لا يكفي لاستبعاد التحسين.
بين أول \(14\) نقطة مولّدة، يكون أقرب زوج هو
$$ (18885138,9652189),\qquad(19047286,9130354). $$
وفروق الإحداثيات هي
$$\Delta x=162148,\qquad \Delta y=-521835,$$
لذلك فإن مربع المسافة يساوي
$$162148^2+(-521835)^2=26291973904+272311767225=298603741129.$$
ومن ثم
$$d(14)=\sqrt{298603741129}\approx 546446.466846479,$$
وهو بالضبط مقدار التحقق الذي تعيده التطبيقات.
تبدأ تطبيقات C++ وPython وJava بالطريقة نفسها: توليد النقاط الحتمية، ثم ترتيبها حسب \(x\)، ثم حفظ أفضل قيمة حالية على هيئة مربع مسافة باستخدام حساب صحيح.
تستخدم تطبيقات C++ وPython أسلوب sweep-line. أثناء التحرك من اليسار إلى اليمين تُزال النقاط التي أصبح بعدها في \(x\) أكبر من أفضل مسافة حالية. أما النقاط التي تبقى في البنية النشطة فتكون مرتبة حسب \(y\)، ولذلك لا يُفحص إلا الشريط الضيق في \(y\) القادر على تحسين الجواب.
أما تطبيق Java فيستخدم القسمة والتغلب. فهو يحل النصف الأيسر والنصف الأيمن بصورة تراجعية، ويحتفظ بأصغر مربع مسافة بينهما، ثم يفحص فقط الشريط المركزي القريب من إحداثي \(x\) الوسيط. بعد ترتيب هذا الشريط حسب \(y\)، تتوقف المقارنات ما إن يصبح فرق \(y\) وحده كافيًا لاستبعاد أي تحسن.
وفي جميع التطبيقات تكون الخطوة الأخيرة هي أخذ جذر تربيعي واحد ثم تنسيق الناتج إلى تسعة منازل عشرية.
توليد النقاط يحتاج إلى \(O(k)\) زمنًا و\(O(k)\) ذاكرة. أما الفرز فيكلف \(O(k\log k)\). يحقق تطبيق Java القائم على القسمة والتغلب الحد القياسي \(O(k\log k)\) زمنيًا مع \(O(k)\) ذاكرة إضافية. كما تستخدم تطبيقات C++ وPython القائمة على sweep-line ذاكرة \(O(k)\) أيضًا، وهي مصممة لتبقى قريبة من \(O(k\log k)\) على هذه البيانات لأن كل نقطة تدخل البنية النشطة مرة واحدة وتغادرها مرة واحدة، ولأن البحث في كل خطوة يقتصر على شريط مرشحين ضيق جدًا.