Problem 165 asks for the number of distinct true intersection points among 5000 line segments generated by a deterministic pseudo-random process. Each segment is determined by four consecutive values from the sequence, so the geometric input is fixed even though it looks random.
A true intersection means a single point that lies strictly inside both segments. Endpoint touches are excluded, and collinear overlaps are excluded as well. The two real difficulties are deciding that strict condition correctly for every pair of segments and making sure that the same geometric point is not counted twice when different segment pairs meet there.
The solution has four mathematical ingredients: generating the segments, testing whether two segments cross in their interiors, computing the crossing point exactly, and storing those points in a canonical form so duplicates collapse automatically.
The sequence used by the problem is
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
and then
$$t_n=s_n \bmod 500.$$
The \(n\)-th segment is therefore
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
All coordinates are integers between 0 and 499, so every segment endpoint lies on the integer lattice inside a \(500\times500\) box. That bounded integer structure is what makes an exact integer-and-rational solution practical.
For three points \(A\), \(B\), \(C\), define the signed area determinant
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
The sign of \(\Delta(A,B,C)\) tells us on which side of the directed line \(AB\) the point \(C\) lies. For two segments \(AB\) and \(CD\), a proper interior crossing occurs exactly when \(C\) and \(D\) lie on opposite sides of line \(AB\), and simultaneously \(A\) and \(B\) lie on opposite sides of line \(CD\). In formulas,
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
The strict inequality is the key detail. If one determinant is zero, then one endpoint lies on the other supporting line, which means an endpoint touch or a collinear case rather than a true interior intersection. So the test used by the implementations rejects all non-strict cases automatically.
The same condition can be written parametrically. Write
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
If the two supporting lines are not parallel, there is a unique solution of
$$A+t(B-A)=C+u(D-C).$$
With \(r=B-A\) and \(s=D-C\), the denominator is the 2D determinant
$$\operatorname{den}=r\times s,$$
and the numerators are
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
Then the crossing point lies strictly inside both segments exactly when
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
after interpreting the inequalities with the sign of \(\operatorname{den}\). One implementation uses this form directly, while the others use the orientation-sign version above. They are the same determinant test written in two different languages of geometry.
Once two segments are known to intersect properly, the intersection point must be stored exactly. Floating-point coordinates would be risky here because two algebraically identical points can arrive through different segment pairs and round slightly differently.
For the line through \(A=(x_1,y_1)\) and \(B=(x_2,y_2)\), write
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$$
and similarly for the line through \(C=(x_3,y_3)\) and \(D=(x_4,y_4)\):
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
Then Cramer's rule gives
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
The denominator is normalized to be positive, and then the \(x\)-coordinate and \(y\)-coordinate are each reduced by their own greatest common divisor. The canonical representation is therefore the quadruple
$$\left(\frac{x_{\text{num}}}{x_{\text{den}}},\frac{y_{\text{num}}}{y_{\text{den}}}\right),$$
stored as four integers \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). Because the fractions are reduced and denominators are made positive, equal geometric points receive exactly the same key.
The sample segments
$$((46,53),(17,62))\quad\text{and}\quad((46,70),(22,40))$$
produce the unique true intersection among the three sample segments checked by the implementation.
For these two segments,
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
Also \(C-A=(0,17)\), so
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
Since
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
the intersection is strictly interior to both segments. Using \(A+t(B-A)\) with \(t=408/1086=68/181\), we get
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
That exact rational point is what gets inserted into the set. Any later segment pair producing the same point would reduce to the same canonical quadruple and would therefore not be counted twice.
The problem does not ask for the number of intersecting segment pairs. It asks for the number of distinct true intersection points. Several different pairs can meet at the same point, so after a pair passes the strict crossing test, the correct mathematical object to store is the point itself, not the pair. The implementations therefore turn every valid crossing into one exact rational point and let the set structure remove duplicates.
The C++, Python, and Java implementations begin by generating the deterministic sequence, reducing each term modulo 500, and grouping every four values into one segment. This reproduces the problem input exactly and avoids any dependence on floating-point randomness or external data.
The main loop examines all \(\binom{5000}{2}\) unordered pairs of segments. The C++ and Python implementations evaluate the four oriented-area determinants and require opposite signs on both sides. The Java implementation computes the same geometry through the denominator and the two segment parameters, then checks that both parameters lie strictly between 0 and 1. Although the formulas look different, both approaches reject parallel pairs, endpoint touches, and overlaps for the same mathematical reason.
Whenever a pair truly intersects, the implementation computes the point with integer arithmetic and reduces the resulting rational coordinates. The C++ and Python implementations store the reduced quadruple directly in an ordered set. The Java implementation reduces the same rational data and compresses it into a hashable key for a hash set. In all three cases, the canonicalized rational representation is the mechanism that turns repeated geometric points into one stored object.
With \(N=5000\) segments, the algorithm checks
$$\binom{5000}{2}=12{,}497{,}500$$
segment pairs, so the running time is \(O(N^2)\). Each pair requires only constant-time integer arithmetic, plus a few \(\gcd\) reductions when an actual intersection is found.
Memory usage is \(O(N+K)\), where \(N\) accounts for the stored segments and \(K\) is the number of distinct true intersection points that survive de-duplication. For this problem size, the quadratic scan is entirely feasible, and the exact-rational storage keeps the count mathematically correct.
Problem 165 verlangt die Anzahl verschiedener echter Schnittpunkte unter 5000 Strecken, die aus einem deterministischen pseudozufälligen Prozess erzeugt werden. Jede Strecke wird aus vier aufeinanderfolgenden Folgengliedern gebildet, daher ist die gesamte Geometrie fest vorgegeben, auch wenn sie zufällig aussieht.
Ein echter Schnittpunkt ist ein einzelner Punkt im Inneren beider Strecken. Berührungen an Endpunkten zählen nicht, kollineare Überdeckungen ebenfalls nicht. Die eigentliche Arbeit besteht also darin, diese strenge Bedingung korrekt zu testen und gleiche geometrische Punkte trotz unterschiedlicher Streckenpaare nur einmal zu zählen.
Die Lösung kombiniert vier Bausteine: die Erzeugung der Strecken, einen strengen Schnitt-Test über orientierte Flächeninhalte, die exakte Berechnung des Schnittpunkts und eine kanonische rationale Darstellung zur Deduplikation.
Die im Problem verwendete Folge ist
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
und danach
$$t_n=s_n \bmod 500.$$
Die \(n\)-te Strecke ist damit
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
Alle Koordinaten liegen also ganzzahlig zwischen 0 und 499. Genau diese diskrete Struktur macht es möglich, den gesamten Schnittprozess mit exakter Arithmetik statt mit Fließkommazahlen durchzuführen.
Für drei Punkte \(A\), \(B\), \(C\) definieren wir den Determinantenwert
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
Das Vorzeichen von \(\Delta(A,B,C)\) sagt, auf welcher Seite der gerichteten Geraden \(AB\) der Punkt \(C\) liegt. Zwei Strecken \(AB\) und \(CD\) schneiden sich genau dann echt im Inneren, wenn \(C\) und \(D\) auf verschiedenen Seiten von \(AB\) liegen und gleichzeitig \(A\) und \(B\) auf verschiedenen Seiten von \(CD\). Also gilt
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
Dass die Ungleichungen strikt sind, ist entscheidend. Ein Nullwert bedeutet, dass ein Endpunkt auf der anderen Trägergeraden liegt, also Berührung oder Kollinearität statt eines echten Innenschnitts. Genau dadurch fallen Randfälle automatisch heraus.
Dieselbe Geometrie kann man auch parametrisch schreiben:
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
Für nicht parallele Trägergeraden löst man
$$A+t(B-A)=C+u(D-C).$$
Mit \(r=B-A\) und \(s=D-C\) erhält man
$$\operatorname{den}=r\times s,$$
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
Ein echter Schnitt liegt genau dann vor, wenn
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
wobei die Richtung der Ungleichungen an das Vorzeichen von \(\operatorname{den}\) angepasst wird. Eine Implementierung benutzt diese Form direkt, die anderen arbeiten mit Vorzeichen der orientierten Flächeninhalte. Mathematisch ist es derselbe Test.
Nach einem erfolgreichen Test muss der Schnittpunkt exakt gespeichert werden. Fließkommaarithmetik wäre gefährlich, weil derselbe Punkt von verschiedenen Streckenpaaren aus leicht unterschiedlich gerundet werden könnte.
Für die Gerade durch \(A=(x_1,y_1)\) und \(B=(x_2,y_2)\) setzen wir
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$$
und entsprechend für die Gerade durch \(C=(x_3,y_3)\) und \(D=(x_4,y_4)\)
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
Mit Cramers Regel folgt
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
Der Nenner wird positiv normiert, anschließend werden \(x\) und \(y\) jeweils mit ihrem eigenen ggT gekürzt. So entsteht die kanonische Darstellung als vier Integer \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). Gleiche geometrische Punkte führen dann zwangsläufig zum gleichen Schlüssel.
Die Strecken
$$((46,53),(17,62)),\quad((46,70),(22,40))$$
liefern genau den einen echten Schnittpunkt aus dem Dreierbeispiel, das von der Implementierung geprüft wird.
Hier gilt
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
Außerdem ist \(C-A=(0,17)\), also
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
Wegen
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086$$
liegt der Schnittpunkt strikt im Inneren beider Strecken. Mit \(t=408/1086=68/181\) erhält man
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
Genau dieser rationale Punkt wird gespeichert. Würde später ein anderes Streckenpaar denselben Punkt erzeugen, bekäme es nach der Kürzung dieselbe kanonische Darstellung und würde daher nicht doppelt gezählt.
Gesucht ist nicht die Anzahl schneidender Streckenpaare, sondern die Anzahl verschiedener echter Schnittpunkte. Mehrere Paare können sich im selben Punkt treffen. Deshalb speichert man nach dem Test nicht das Paar, sondern den Schnittpunkt selbst, und zwar in exakter rationaler Form. Die Datenstruktur für Mengen erledigt dann die Deduplikation exakt und verlustfrei.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst die deterministische Folge, reduzieren jedes Glied modulo 500 und fassen immer vier Werte zu einer Strecke zusammen. Damit wird die Eingabe des Problems exakt reproduziert.
Danach werden alle \(\binom{5000}{2}\) ungeordneten Streckenpaare untersucht. C++ und Python berechnen die vier orientierten Flächenwerte und verlangen auf beiden Seiten entgegengesetzte Vorzeichen. Java arbeitet mit Nenner und Parametern \(t\) und \(u\) und fordert, dass beide strikt zwischen 0 und 1 liegen. Beides ist dieselbe geometrische Bedingung in unterschiedlicher Schreibweise.
Bei jedem echten Schnittpunkt wird die Koordinate mit Integerarithmetik berechnet und als gekürztes rationales Tupel abgelegt. C++ und Python speichern dieses Tupel direkt in einer geordneten Menge. Java reduziert dieselben rationalen Daten und wandelt sie in einen hashbaren Schlüssel für eine Hash-Menge um. In allen drei Fällen sorgt die kanonische Darstellung dafür, dass gleiche Punkte zusammenfallen.
Für \(N=5000\) Strecken müssen
$$\binom{5000}{2}=12{,}497{,}500$$
Paare geprüft werden. Die Laufzeit ist daher \(O(N^2)\). Pro Paar fallen nur konstante viele Ganzzahloperationen an; \(\gcd\)-Berechnungen sind nur bei tatsächlich gefundenen Schnittpunkten nötig.
Der Speicherbedarf ist \(O(N+K)\), wobei \(N\) für die gespeicherten Strecken und \(K\) für die Zahl der verschiedenen echten Schnittpunkte steht. Für die Problemgröße ist dieser quadratische Ansatz problemlos praktikabel, und die exakte rationale Repräsentation verhindert Zählfehler.
Problem 165, deterministik bir pseudo-random üreticiyle tanımlanan 5000 doğru parçası arasındaki farklı gerçek kesişim noktalarının sayısını ister. Her parça, diziden gelen ardışık dört değerden oluşur; bu yüzden veri kümesi rastgele görünse de tamamen sabittir.
Gerçek kesişim, iki parçanın iç noktasında oluşan tek bir ortak noktadır. Uç noktadan değmeler sayılmaz; kolineer örtüşmeler de sayılmaz. Dolayısıyla çözümün özü, bu sıkı geometrik koşulu doğru biçimde test etmek ve aynı noktaya gelen farklı parça çiftlerini tek bir nokta olarak saymaktır.
Çözüm dört parçadan oluşur: doğru parçalarını üretmek, iki parçanın gerçekten içten kesişip kesişmediğini belirlemek, kesişim noktasını tam olarak hesaplamak ve bu noktaları kanonik rasyonel biçimde saklayarak tekrarları elemek.
Kullanılan dizi
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
ve ardından
$$t_n=s_n \bmod 500$$
şeklindedir. Buna göre \(n\). doğru parçası
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000$$
olarak tanımlanır. Bütün koordinatlar 0 ile 499 arasında tam sayıdır. Bu sınırlı tam sayı yapısı, hem kesişim testinin hem de nokta temsilinin kayan nokta yerine tam aritmetikle yürütülmesini mümkün kılar.
Üç nokta \(A\), \(B\), \(C\) için
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x)$$
tanımını yapalım. Bu determinant, \(C\) noktasının yönlü \(AB\) doğrusunun hangi tarafında olduğunu söyler. İki parça \(AB\) ve \(CD\), ancak ve ancak \(C\) ile \(D\) noktaları \(AB\) doğrusunun zıt taraflarında ve aynı anda \(A\) ile \(B\) noktaları \(CD\) doğrusunun zıt taraflarında ise gerçek bir iç kesişim oluşturur. Yani
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
Buradaki sıkılık çok önemlidir. Bir determinant sıfır olursa, bir uç nokta diğer parçanın taşıyıcı doğrusu üzerindedir; bu da ya uçtan temas ya da kolineer durum demektir. Dolayısıyla kodun kullandığı sıkı işaret testi, gerçek olmayan kesişimleri otomatik olarak dışarıda bırakır.
Aynı geometri parametrik olarak da yazılabilir:
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
Parçaların taşıyıcı doğruları paralel değilse
$$A+t(B-A)=C+u(D-C)$$
denkleminin tek çözümü vardır. \(r=B-A\) ve \(s=D-C\) dersek
$$\operatorname{den}=r\times s,$$
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r$$
olur. Gerçek kesişim koşulu, \(\operatorname{den}\)'in işareti dikkate alınarak
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1$$
şeklindedir. Uygulamalardan biri bu formu doğrudan kullanır; diğerleri yönlü alan işaretlerini kullanır. Matematiksel olarak bunlar aynı determinant hesabıdır.
Bir parça çifti gerçek kesişim veriyorsa, noktanın tam olarak saklanması gerekir. Aksi halde kayan nokta yuvarlaması, aynı noktayı farklı parça çiftleri için farklı görünümlerde üretebilir.
\(A=(x_1,y_1)\) ve \(B=(x_2,y_2)\) üzerinden geçen doğru için
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1$$
ve \(C=(x_3,y_3)\), \(D=(x_4,y_4)\) üzerinden geçen doğru için
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3$$
tanımlanır. Cramer kuralı ile
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}$$
elde edilir. Payda pozitif yapılır; sonra \(x\) ve \(y\) kendi \(\gcd\)'leri ile ayrı ayrı sadeleştirilir. Böylece nokta
$$\left(\frac{x_{\text{num}}}{x_{\text{den}}},\frac{y_{\text{num}}}{y_{\text{den}}}\right)$$
biçiminde, dört tam sayıdan oluşan kanonik bir anahtarla temsil edilir. Aynı geometrik nokta her zaman aynı anahtara indirgenir.
Uygulamanın doğruladığı üç örnek parçadan gerçek kesişim veren çift şudur:
$$((46,53),(17,62)),\quad((46,70),(22,40)).$$
Bu iki parça için
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
Ayrıca \(C-A=(0,17)\) olduğundan
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493$$
bulunur. Çünkü
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
kesişim her iki parçanın da içindedir. \(t=408/1086=68/181\) yazarsak
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}$$
elde edilir. Sete eklenen şey tam olarak bu rasyonel noktadır. Aynı nokta başka bir parça çiftiyle tekrar oluşsa bile sadeleşmiş temsil aynı olacağından ikinci kez sayılmaz.
İstenen nicelik, kesişen parça çiftlerinin sayısı değildir; farklı gerçek kesişim noktalarının sayısıdır. Birden fazla parça çifti aynı noktada buluşabilir. Bu yüzden doğru matematiksel nesne, testten geçen her çift için “çiftin kimliği” değil “noktanın kendisi”dir. Uygulamalar da tam olarak bunu yapar: her gerçek kesişimi tek bir kanonik rasyonel noktaya dönüştürür ve set yapısına bırakır.
C++, Python ve Java uygulamaları önce deterministik diziyi üretir, her terimi 500 moduna indirger ve her dört değeri bir doğru parçası olarak gruplayarak problem girişini aynen kurar.
Ana döngü, \(\binom{5000}{2}\) tane sırasız parça çiftini tarar. C++ ve Python sürümleri dört yönlü alan determinantını hesaplayıp iki tarafta da zıt işaret ister. Java sürümü aynı geometriyi parametreler ve payda üzerinden yazar; \(t\) ve \(u\) değerlerinin sıkı biçimde 0 ile 1 arasında kalmasını zorunlu kılar. İki yol da paralel, uçtan temas eden veya örtüşen çiftleri dışlar.
Gerçek kesişim bulunduğunda koordinatlar tam sayı aritmetiğiyle hesaplanır ve sadeleştirilmiş rasyonel biçime çevrilir. C++ ve Python bunu doğrudan bir kümeye koyar. Java ise aynı rasyonel bilgiyi hash anahtarına dönüştürerek saklar. Temel fikir aynıdır: aynı nokta aynı temsile sahip olur.
\(N=5000\) için
$$\binom{5000}{2}=12{,}497{,}500$$
parça çifti incelenir; dolayısıyla zaman karmaşıklığı \(O(N^2)\)'dir. Her çiftte sabit sayıda tam sayı işlemi yapılır; \(\gcd\) sadeleştirmesi ise yalnızca gerçek kesişim çıktığında gerekir.
Bellek karmaşıklığı \(O(N+K)\)'dir. Burada \(N\) parça listesini, \(K\) ise tekrarlar elendikten sonra elde kalan farklı gerçek kesişim noktalarını gösterir. Problem boyutunda bu tarama gayet uygulanabilirdir ve tam rasyonel temsil sayım hatalarını önler.
El Problema 165 pide contar cuántos puntos de intersección verdadera distintos aparecen entre 5000 segmentos generados por un proceso pseudoaleatorio determinista. Cada segmento se forma con cuatro valores consecutivos de la sucesión, así que la entrada geométrica queda completamente fijada.
Una intersección verdadera es un único punto situado estrictamente en el interior de ambos segmentos. No se cuentan toques en extremos ni solapamientos colineales. Por eso la solución debe resolver dos cuestiones: detectar correctamente esa condición estricta y evitar contar varias veces el mismo punto cuando diferentes pares de segmentos pasan por él.
La idea completa tiene cuatro piezas: generar los segmentos, decidir si dos segmentos se cruzan en sus interiores, calcular el punto de cruce con aritmética exacta y guardar cada punto con una representación racional canónica.
La sucesión del problema es
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
seguida de
$$t_n=s_n \bmod 500.$$
Así, el segmento \(n\)-ésimo es
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
Todas las coordenadas son enteras entre 0 y 499. Esa estructura discreta es importante porque garantiza que los determinantes y los puntos de intersección se pueden manejar exactamente con enteros y racionales.
Para tres puntos \(A\), \(B\), \(C\), definimos
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
El signo de \(\Delta(A,B,C)\) indica en qué lado de la recta orientada \(AB\) cae el punto \(C\). Dos segmentos \(AB\) y \(CD\) se cortan propiamente en sus interiores si y solo si \(C\) y \(D\) están en lados opuestos de la recta \(AB\), y al mismo tiempo \(A\) y \(B\) están en lados opuestos de la recta \(CD\). Eso se escribe como
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
La desigualdad estricta es lo que excluye los casos no válidos. Si algún determinante vale cero, un extremo cae sobre la recta soporte del otro segmento, lo que corresponde a un toque en un extremo o a un caso colineal, no a una intersección verdadera.
La misma condición también puede expresarse con parámetros. Escribimos
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
Cuando las rectas no son paralelas, resolvemos
$$A+t(B-A)=C+u(D-C).$$
Si \(r=B-A\) y \(s=D-C\), entonces
$$\operatorname{den}=r\times s,$$
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
La intersección está estrictamente dentro de ambos segmentos exactamente cuando
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
teniendo en cuenta el signo de \(\operatorname{den}\). Una implementación usa directamente esta forma, mientras que las otras usan signos de orientaciones. Son dos caras de la misma cuenta determinantal.
Una vez detectado un cruce válido, el punto debe almacenarse de forma exacta. Usar números en coma flotante sería peligroso porque el mismo punto podría aparecer con redondeos distintos cuando lo generan pares diferentes.
Para la recta que pasa por \(A=(x_1,y_1)\) y \(B=(x_2,y_2)\), definimos
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$$
y para la recta que pasa por \(C=(x_3,y_3)\) y \(D=(x_4,y_4)\), definimos
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
La regla de Cramer da
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
Se normaliza el signo del denominador para hacerlo positivo y luego se reducen \(x\) e \(y\) por separado con su propio \(\gcd\). El resultado es una clave canónica formada por cuatro enteros \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). Si dos pares de segmentos producen el mismo punto, generan exactamente la misma clave.
Los segmentos
$$((46,53),(17,62)),\quad((46,70),(22,40))$$
son el único par con intersección verdadera dentro de los tres segmentos de muestra comprobados por la implementación.
Aquí tenemos
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
Además \(C-A=(0,17)\), de modo que
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
Como
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
el cruce cae estrictamente en el interior de ambos segmentos. Con \(t=408/1086=68/181\), obtenemos
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
Ese punto racional exacto es el que se inserta en el conjunto. Si más adelante otro par produce el mismo cruce, la reducción lo llevará a la misma representación y no se contará dos veces.
El problema no pide cuántos pares de segmentos se cruzan, sino cuántos puntos de intersección verdadera distintos existen. Distintos pares pueden compartir el mismo punto. Por eso, después de validar un cruce, el objeto matemático correcto es el punto mismo, expresado como racional exacto, y no la identidad del par que lo produjo.
Las implementaciones en C++, Python y Java generan la sucesión determinista, toman cada término módulo 500 y agrupan cada bloque de cuatro valores para construir exactamente los 5000 segmentos del problema.
El núcleo del programa recorre los \(\binom{5000}{2}\) pares no ordenados. C++ y Python usan las cuatro orientaciones con signo. Java usa el denominador y los parámetros de la forma paramétrica. Ambas variantes descartan pares paralelos, contactos en extremos y solapamientos porque implementan la misma condición geométrica estricta.
Cuando un par es válido, el punto se calcula con aritmética entera y se reduce a una forma racional canónica. C++ y Python almacenan la cuádrupla reducida directamente en un conjunto ordenado. Java reduce la misma información y la convierte en una clave apta para un conjunto hash. En todos los casos, la deduplicación depende de la normalización exacta.
Con \(N=5000\), el algoritmo examina
$$\binom{5000}{2}=12{,}497{,}500$$
pares de segmentos, así que el tiempo total es \(O(N^2)\). Cada par requiere solo unas pocas operaciones enteras, y las reducciones por \(\gcd\) aparecen únicamente cuando se encuentra una intersección verdadera.
La memoria es \(O(N+K)\), donde \(N\) corresponde al almacenamiento de los segmentos y \(K\) al número de puntos de intersección verdadera distintos que sobreviven tras la deduplicación. Para este tamaño, el barrido cuadrático es perfectamente razonable.
第 165 题要求统计 5000 条线段之间有多少个不同的“真交点”。这些线段不是任意给出的，而是由一个确定性的伪随机递推生成的，所以输入看起来随机，实际上完全固定。
所谓真交点，是指两个线段在各自内部相交于唯一一点。端点相碰不算，整段共线重叠也不算。于是问题的核心就变成两件事：第一，如何严格而无歧义地判定“内部相交”；第二，如何保证同一个几何点即使由不同线段对产生，也只计数一次。
完整思路由四部分组成：生成线段、判定两条线段是否发生严格内部相交、精确求出交点坐标、把交点化为规范化有理数形式以便去重。
题目使用的序列满足
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
然后定义
$$t_n=s_n \bmod 500.$$
于是第 \(n\) 条线段为
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
所有端点坐标都落在 0 到 499 的整数范围内。这个事实非常重要，因为它意味着判定公式中的所有量都可以用整数表示，而真正的交点如果存在，则一定是有理数坐标，因此完全可以避免浮点误差。
对三个点 \(A\)、\(B\)、\(C\)，定义二维行列式
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
\(\Delta(A,B,C)\) 的符号表示点 \(C\) 位于有向直线 \(AB\) 的哪一侧。设两条线段分别为 \(AB\) 和 \(CD\)。它们发生真交点，当且仅当 \(C\) 与 \(D\) 分别位于直线 \(AB\) 的两侧，同时 \(A\) 与 \(B\) 也分别位于直线 \(CD\) 的两侧。写成公式就是
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
这里必须是严格小于零，而不是小于等于零。因为一旦某个行列式等于零，就说明某个端点落在另一条支撑直线上，这对应的是端点接触或共线情形，不属于题目要求的真交点。正是这个“严格”条件，让端点接触与重叠都被自动排除。
同一个判定也可以写成参数形式。设
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
若两条支撑直线不平行，则存在唯一解满足
$$A+t(B-A)=C+u(D-C).$$
记 \(r=B-A\)、\(s=D-C\)，则分母是
$$\operatorname{den}=r\times s,$$
而两个参数的分子分别是
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
那么交点严格位于两条线段内部，当且仅当
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
同时要根据 \(\operatorname{den}\) 的符号调整不等式方向。三份实现中，有的直接使用四个有向面积的符号，有的直接检查这两个参数是否落在开区间 \((0,1)\) 内。两种写法在数学上完全等价，底层都是同一个二维行列式。
找到真交点之后，不能用浮点数保存坐标。原因很简单：同一个点可能由不同线段对算出来，如果采用浮点数，舍入差异可能导致本应相同的点被误认为不同。
设第一条直线经过 \(A=(x_1,y_1)\)、\(B=(x_2,y_2)\)，可写成
$$a_1x+b_1y=c_1,$$
其中
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1.$$
第二条直线经过 \(C=(x_3,y_3)\)、\(D=(x_4,y_4)\)，同理有
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
由 Cramer 法则得到
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
实现会先把分母规范成正数，然后分别对 \(x\) 与 \(y\) 的分子分母做约分。于是每个交点都被表示成一个规范化四元组
$$\left(x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}}\right).$$
只要两个交点在几何上相同，它们约分后的四元组就一定完全一致，因此非常适合作为集合中的键。
实现里还检查了题目给出的三个示例线段，其中真正相交的一对是
$$((46,53),(17,62)),\quad((46,70),(22,40)).$$
对这两条线段，有
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
再计算 \(C-A=(0,17)\)，于是
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
因为
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
所以交点严格落在两条线段内部。又因为 \(t=408/1086=68/181\)，代回第一条线段参数方程可得
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
这就是被插入集合的精确交点。以后如果别的线段对也在这个位置相交，最终得到的约分四元组仍然相同，因此不会重复计数。
题目要的是不同真交点的个数，而不是相交线段对的个数。多个不同的线段对完全可能在同一个位置相交。因此，当一对线段通过严格判定之后，真正应该存储的数学对象是那个交点本身，而不是这对线段的编号。把交点规范化为精确有理数之后，再交给集合去重，正好与题意完全一致。
C++、Python 和 Java 实现都先生成确定性序列，对每一项取模 500，然后每四个数拼成一条线段。这样构造出的输入与题目规定完全一致。
主循环枚举全部 \(\binom{5000}{2}\) 个无序线段对。C++ 与 Python 版本直接检查四个有向面积的符号。Java 版本则计算参数分母与分子，判断两个参数是否严格落在 0 和 1 之间。虽然形式不同，本质上是同一个二维行列式判定。
一旦发现真交点，实现就用整数运算求出精确坐标，并把两个坐标分别约成最简分数。C++ 和 Python 直接把四元组放进集合。Java 先得到同样的规范化有理数数据，再压成可哈希的键放进哈希集合。三种实现的共同点都是：相同几何点必须映射成相同的规范化表示。
当 \(N=5000\) 时，需要检查的线段对数量为
$$\binom{5000}{2}=12{,}497{,}500.$$
因此总时间复杂度是 \(O(N^2)\)。每次检查只涉及常数次整数运算；只有在确实发现真交点时，才需要额外做几次 \(\gcd\) 约分。
空间复杂度是 \(O(N+K)\)，其中 \(N\) 来自线段数组，\(K\) 是去重之后保留下来的不同真交点数。对于本题给定的规模，这样的二次枚举完全可行，而且精确有理数表示保证了结果不会因数值误差而出错。
В задаче 165 нужно посчитать число различных истинных точек пересечения среди 5000 отрезков, построенных по детерминированному псевдослучайному правилу. Каждый отрезок задается четырьмя последовательными значениями последовательности, так что геометрические данные полностью фиксированы.
Истинное пересечение означает единственную общую точку, лежащую строго внутри обоих отрезков. Касание концами не учитывается, коллинеарное наложение тоже не учитывается. Поэтому надо не просто проверить пересечение, а проверить именно строгий внутренний случай и затем корректно устранить повторы одинаковых точек.
Решение состоит из четырех частей: генерация отрезков, строгий тест пересечения, точное вычисление координат точки пересечения и каноническое хранение этой точки в рациональном виде.
Используемая последовательность имеет вид
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
после чего берется
$$t_n=s_n \bmod 500.$$
Тогда \(n\)-й отрезок равен
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
Все координаты являются целыми числами от 0 до 499. Это означает, что вся проверка может выполняться на целых детерминантах, а точка пересечения при необходимости выражается точными рациональными числами.
Для трех точек \(A\), \(B\), \(C\) введем величину
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
Ее знак показывает, по какую сторону от ориентированной прямой \(AB\) лежит точка \(C\). Два отрезка \(AB\) и \(CD\) имеют истинное пересечение тогда и только тогда, когда точки \(C\) и \(D\) лежат по разные стороны от прямой \(AB\), а точки \(A\) и \(B\) лежат по разные стороны от прямой \(CD\). Формально это записывается так:
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
Строгость здесь принципиальна. Если какой-то детерминант равен нулю, значит один конец лежит на опорной прямой другого отрезка. Это соответствует касанию концом или коллинеарному случаю, а не строгому внутреннему пересечению.
Ту же геометрию можно записать в параметрической форме:
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
Если опорные прямые не параллельны, то из уравнения
$$A+t(B-A)=C+u(D-C)$$
получается единственное решение. Обозначив \(r=B-A\) и \(s=D-C\), получаем
$$\operatorname{den}=r\times s,$$
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
Тогда точка лежит строго внутри обоих отрезков тогда и только тогда, когда
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
с учетом знака \(\operatorname{den}\). Одна реализация использует именно эту форму, а другие опираются на знаки ориентированных площадей. С математической точки зрения это одна и та же проверка.
После успешного теста точку пересечения нужно хранить точно. Если использовать числа с плавающей запятой, один и тот же геометрический пункт может быть получен с разным округлением для разных пар отрезков.
Для прямой через \(A=(x_1,y_1)\) и \(B=(x_2,y_2)\) положим
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$$
а для прямой через \(C=(x_3,y_3)\) и \(D=(x_4,y_4)\)
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
По правилу Крамера имеем
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
Затем знак знаменателя нормализуется, а координаты \(x\) и \(y\) сокращаются по отдельности на свой \(\gcd\). Так получается канонический ключ из четырех целых чисел \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). Совпадающие точки неизбежно приводят к одному и тому же ключу.
Среди трех тестовых отрезков, которые проверяет реализация, единственное истинное пересечение дают
$$((46,53),(17,62)),\quad((46,70),(22,40)).$$
Здесь
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
Кроме того, \(C-A=(0,17)\), поэтому
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
Так как
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
точка действительно лежит строго внутри обоих отрезков. Подставляя \(t=408/1086=68/181\), получаем
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
Именно эта рациональная точка помещается в множество. Если какая-то другая пара отрезков пересечется в той же точке, после сокращения она даст тот же канонический ключ и не увеличит ответ повторно.
Задача спрашивает не число пересекающихся пар, а число различных истинных точек пересечения. Несколько разных пар могут проходить через один и тот же геометрический пункт. Поэтому после проверки следует сохранять саму точку пересечения в точной рациональной форме, а не информацию о паре отрезков.
Реализации на C++, Python и Java сначала строят детерминированную последовательность, берут каждый член по модулю 500 и собирают из каждых четырех чисел один отрезок. Так воспроизводится точный вход задачи.
Основной цикл перебирает все \(\binom{5000}{2}\) неупорядоченные пары. Варианты на C++ и Python используют четыре ориентированных детерминанта. Вариант на Java использует знаменатель и два параметра параметрического уравнения. Оба подхода эквивалентны и отбрасывают параллельные случаи, касания концами и наложения.
Для каждой корректной точки пересечения координаты вычисляются в точной целочисленной арифметике, затем сокращаются до канонического рационального вида. C++ и Python кладут сокращенную четверку прямо в множество. Java превращает те же сокращенные рациональные данные в хешируемый ключ и хранит его в hash set. Во всех трех реализациях одинаковые точки отождествляются именно благодаря этой нормализации.
При \(N=5000\) требуется проверить
$$\binom{5000}{2}=12{,}497{,}500$$
пар отрезков, поэтому время работы равно \(O(N^2)\). На каждую пару приходится лишь постоянное число целочисленных операций; вычисления \(\gcd\) нужны только для найденных пересечений.
Память составляет \(O(N+K)\), где \(N\) связано с хранением отрезков, а \(K\) обозначает число различных истинных точек пересечения после удаления повторов. Для размера задачи такой квадратичный перебор вполне приемлем.
تطلب المسألة 165 حساب عدد نقاط التقاطع الحقيقي المميزة بين 5000 قطعة مستقيمة مولدة بعملية شبه عشوائية حتمية. كل قطعة تُبنى من أربعة حدود متتالية من المتتالية، لذلك فإن المعطيات الهندسية ثابتة تمامًا رغم أنها تبدو عشوائية.
المقصود بالتقاطع الحقيقي هو نقطة وحيدة تقع داخل القطعتين معًا، لا عند الأطراف. لذلك لا تُحسب ملامسات النهايات، ولا حالات التراكب على خط واحد. جوهر الحل هو إذن اختبار هذا الشرط الصارم بدقة، ثم منع عدّ النقطة نفسها أكثر من مرة إذا نتجت من أزواج مختلفة من القطع.
يتكون الحل من أربع أفكار مترابطة: توليد القطع المستقيمة، تحديد ما إذا كان زوج منها يتقاطع تقاطعًا داخليًا صارمًا، حساب نقطة التقاطع حسابًا دقيقًا، ثم تخزينها بصيغة كسرية معيارية تسمح بإزالة التكرار.
المتتالية المستخدمة هي
$$s_0=290797,\qquad s_{n+1}=s_n^2 \bmod 50515093,$$
ثم نعرّف
$$t_n=s_n \bmod 500.$$
وعندئذ تكون القطعة رقم \(n\) هي
$$L_n=\bigl((t_{4n-3},t_{4n-2}),(t_{4n-1},t_{4n})\bigr),\qquad 1\le n\le 5000.$$
كل الإحداثيات أعداد صحيحة بين 0 و 499. وهذه البنية الصحيحة المحدودة هي ما يسمح لنا بإجراء جميع الحسابات بالاعتماد على المحددات والأعداد الكسرية الدقيقة بدل الأعداد العائمة.
لثلاث نقاط \(A\) و\(B\) و\(C\)، نعرّف
$$\Delta(A,B,C)=(B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x).$$
إشارة \(\Delta(A,B,C)\) تخبرنا في أي جهة من المستقيم الموجه \(AB\) تقع النقطة \(C\). إذا كانت لدينا القطعتان \(AB\) و\(CD\)، فإن التقاطع الحقيقي يحدث فقط عندما تكون \(C\) و\(D\) على جهتين متعاكستين من المستقيم \(AB\)، وفي الوقت نفسه تكون \(A\) و\(B\) على جهتين متعاكستين من المستقيم \(CD\). أي أن الشرط هو
$$\operatorname{sgn}(\Delta(A,B,C))\operatorname{sgn}(\Delta(A,B,D)) \lt 0,$$
$$\operatorname{sgn}(\Delta(C,D,A))\operatorname{sgn}(\Delta(C,D,B)) \lt 0.$$
والصرامة هنا أساسية. فإذا صار أحد المحددات مساويًا للصفر، فهذا يعني أن أحد الأطراف يقع على مستقيم القطعة الأخرى، أي أننا في حالة ملامسة طرف أو حالة توازٍ وتشارك خطي، لا في حالة تقاطع داخلي حقيقي.
يمكن كتابة الفكرة نفسها بطريقة بارامترية:
$$P(t)=A+t(B-A),\qquad Q(u)=C+u(D-C).$$
إذا لم يكن المستقيمان الحاملان متوازيين، فإن معادلة
$$A+t(B-A)=C+u(D-C)$$
لها حل وحيد. وبوضع \(r=B-A\) و\(s=D-C\) نحصل على
$$\operatorname{den}=r\times s,$$
$$t_{\text{num}}=(C-A)\times s,\qquad u_{\text{num}}=(C-A)\times r.$$
وعندئذ تكون نقطة التقاطع داخل القطعتين على نحو صارم إذا وفقط إذا
$$0 \lt \frac{t_{\text{num}}}{\operatorname{den}} \lt 1,\qquad 0 \lt \frac{u_{\text{num}}}{\operatorname{den}} \lt 1,$$
مع مراعاة إشارة \(\operatorname{den}\) عند تفسير المتباينات. إحدى اللغات في التنفيذ تستعمل هذه الصياغة مباشرة، بينما تستعمل اللغتان الأخريان إشارات المحددات الأربعة. لكن الاختبار الرياضي واحد في الحالتين.
بعد التأكد من وجود تقاطع حقيقي، يجب تخزين الإحداثيات بدقة تامة. استخدام الأعداد العائمة هنا خطر، لأن النقطة نفسها قد تُستخرج من أزواج مختلفة من القطع، وأي فرق في التقريب قد يجعل البرنامج يعدّها نقطتين مختلفتين.
للمستقيم المار بالنقطتين \(A=(x_1,y_1)\) و\(B=(x_2,y_2)\)، نكتب
$$a_1=y_2-y_1,\qquad b_1=x_1-x_2,\qquad c_1=a_1x_1+b_1y_1,$$
وبالمثل للمستقيم المار بالنقطتين \(C=(x_3,y_3)\) و\(D=(x_4,y_4)\):
$$a_2=y_4-y_3,\qquad b_2=x_3-x_4,\qquad c_2=a_2x_3+b_2y_3.$$
تعطي قاعدة كرامر
$$\operatorname{den}=a_1b_2-a_2b_1,$$
$$x=\frac{c_1b_2-c_2b_1}{\operatorname{den}},\qquad y=\frac{a_1c_2-a_2c_1}{\operatorname{den}}.$$
ثم يُطبّع المقام ليصبح موجبًا، ويُختزل كل من \(x\) و\(y\) على حدة بواسطة \(\gcd\). وهكذا تُخزَّن النقطة في صورة رباعية معيارية من الأعداد الصحيحة \((x_{\text{num}},x_{\text{den}},y_{\text{num}},y_{\text{den}})\). أي نقطتين متطابقتين هندسيًا ستعطيان المفتاح نفسه بعد الاختزال.
من بين القطع الثلاث العيّنية التي يتحقق منها التنفيذ، الزوج الوحيد الذي يعطي تقاطعًا حقيقيًا هو
$$((46,53),(17,62)),\quad((46,70),(22,40)).$$
في هذه الحالة
$$r=(-29,9),\qquad s=(-24,-30),\qquad \operatorname{den}=r\times s=1086.$$
كما أن \(C-A=(0,17)\)، لذا
$$t_{\text{num}}=(C-A)\times s=408,\qquad u_{\text{num}}=(C-A)\times r=493.$$
وبما أن
$$0 \lt 408 \lt 1086,\qquad 0 \lt 493 \lt 1086,$$
فإن نقطة التقاطع تقع داخل القطعتين فعلًا. ومع \(t=408/1086=68/181\) نحصل على
$$x=46-\frac{29\cdot68}{181}=\frac{6354}{181},\qquad y=53+\frac{9\cdot68}{181}=\frac{10205}{181}.$$
هذه هي النقطة الكسرية الدقيقة التي تُدرج في المجموعة. وإذا ظهر الزوج نفسه أو زوج آخر يولد النقطة نفسها لاحقًا، فإن التطبيع والاختزال سيقودان إلى المفتاح المعياري نفسه، فلا يحدث عدّ مزدوج.
المسألة لا تسأل عن عدد أزواج القطع المتقاطعة، بل عن عدد نقاط التقاطع الحقيقي المختلفة. لذلك قد تشترك عدة أزواج مختلفة في النقطة نفسها. لهذا السبب، بعد اجتياز اختبار التقاطع، الشيء الصحيح الذي يجب حفظه هو النقطة ذاتها بصيغة كسرية دقيقة، لا هوية الزوج الذي أنشأها.
تبدأ تطبيقات C++ وPython وJava بتوليد المتتالية الحتمية، ثم تأخذ كل حد modulo 500، وبعد ذلك تجمع كل أربعة حدود في قطعة مستقيمة واحدة. بهذه الطريقة تعيد بناء معطيات المسألة كما هي تمامًا.
تستعرض الحلقة الرئيسية جميع الأزواج غير المرتبة وعددها \(\binom{5000}{2}\). في C++ وPython يُستخدم اختبار إشارات المساحات الموجهة الأربع. وفي Java تُحسب الصيغة البارامترية ويُشترط أن يقع كل من المعاملين داخل الفترة المفتوحة \((0,1)\). الطريقتان متكافئتان وتستبعدان التوازي وملامسة الأطراف والتراكب.
عند العثور على تقاطع حقيقي، تُحسب الإحداثيات بحسابات صحيحة ثم تُختزل إلى صورة كسرية معيارية. تطبيقا C++ وPython يخزنان الرباعية المختزلة مباشرة في مجموعة. أما Java فيحوّل البيانات الكسرية نفسها إلى مفتاح قابل للتجزئة ويضعه في مجموعة تجزئة. في كل الحالات، إزالة التكرار تعتمد على هذا التطبيع الدقيق.
عندما يكون \(N=5000\)، فإن عدد الأزواج التي يجب اختبارها هو
$$\binom{5000}{2}=12{,}497{,}500.$$
لذلك يكون الزمن الكلي \(O(N^2)\). وكل زوج يحتاج فقط إلى عدد ثابت من العمليات الصحيحة، بينما تظهر حسابات \(\gcd\) فقط عند وجود تقاطع حقيقي بالفعل.
أما الذاكرة فهي \(O(N+K)\)، حيث يمثّل \(N\) قائمة القطع، ويمثّل \(K\) عدد نقاط التقاطع الحقيقي المختلفة بعد إزالة التكرار. وبالنسبة إلى حجم هذه المسألة، فإن هذا المسح التربيعي عملي تمامًا ودقيق حسابيًا.