Each input row gives one triangle \(ABC\) by listing three integer vertices. The task is to count how many of those triangles contain the origin \(O=(0,0)\) in their interior. Because the tested point never changes, this is not a general point-in-polygon problem; the geometry collapses to a small orientation test involving three signed areas.
Let \(A=(x_1,y_1)\), \(B=(x_2,y_2)\), and \(C=(x_3,y_3)\). The implementations do not use floating-point angles, explicit line intersections, or any iterative search. They evaluate three determinants formed with the origin:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
Geometrically, \(s_1\), \(s_2\), and \(s_3\) are twice the signed areas of the triangles \(OAB\), \(OBC\), and \(OCA\). Their signs tell us whether each consecutive pair of vertex vectors turns counterclockwise or clockwise around the origin.
The whole triangle also has a signed area, namely
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
Expanding this determinant gives the key identity
$$\Delta=s_1+s_2+s_3.$$
So the three subareas cut out by the origin add up to the oriented area of \(ABC\). This is the invariant behind the containment test: the origin is inside exactly when those subareas fit together with a consistent orientation.
A point lies strictly inside a triangle exactly when its barycentric coordinates are all positive. For the origin, the representation
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
has the especially simple closed form
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
Therefore \(O\) is strictly inside \(ABC\) if and only if all three ratios are positive. Since the denominator is common, this happens precisely when \(s_1\), \(s_2\), and \(s_3\) all have the same nonzero sign.
A triangle is convex, so one negative barycentric coordinate already proves that the point lies outside the edge opposite the corresponding vertex. In determinant language, if one of \(s_1,s_2,s_3\) has the opposite sign from the other two, the origin is outside. If one determinant is zero, then \(O\) is collinear with one side, so the origin lies on the boundary rather than in the strict interior.
That is why the decisive condition is simply
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
No divisions are needed in the implementation, and integer arithmetic keeps the test exact.
Consider the triangle
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
Then
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
All three values are positive, so all three barycentric coordinates of the origin are positive as well. Hence the origin lies inside this triangle.
For comparison, with
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
we get
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
The signs are mixed, so one barycentric coordinate is negative and the origin lies outside.
The C++, Python, and Java implementations all scan the triangle list row by row, split each row into six integers, and interpret them as the coordinates of \(A\), \(B\), and \(C\). For each triangle they compute the three determinants \(s_1\), \(s_2\), and \(s_3\) above. There is no preprocessing phase because every triangle can be decided independently.
The final decision is a sign check. The C++ implementation uses the strict form "all three positive or all three negative," which matches strict containment exactly. The Python and Java implementations encode the equivalent "no mixed signs" rule; away from the boundary case \(s_i=0\), it gives the same answer. Every triangle that passes the test increments a running counter, and that counter is the final output.
If there are \(N\) triangles, the algorithm performs a constant amount of work per triangle: three 2-by-2 determinants and a few sign comparisons. The total running time is therefore \(O(N)\).
The geometric test itself uses \(O(1)\) extra space. Some implementations may store input lines before processing them, but the mathematical core needs only the current triangle and the running count. For the Project Euler input size, the computation is effectively instantaneous.
Jede Eingabezeile beschreibt ein Dreieck \(ABC\) durch drei ganzzahlige Eckpunkte. Gesucht ist, wie viele dieser Dreiecke den Ursprung \(O=(0,0)\) im Inneren enthalten. Da stets derselbe Punkt geprüft wird, handelt es sich nicht um ein allgemeines Punkt-in-Polygon-Problem, sondern um einen kleinen Orientierungstest mit drei vorzeichenbehafteten Flächen.
Sei \(A=(x_1,y_1)\), \(B=(x_2,y_2)\) und \(C=(x_3,y_3)\). Die Implementierungen verwenden weder Gleitkommawinkel noch Geradenschnitte. Stattdessen berechnen sie drei Determinanten mit dem Ursprung:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
Geometrisch sind \(s_1\), \(s_2\) und \(s_3\) jeweils das Doppelte der orientierten Flächen von \(OAB\), \(OBC\) und \(OCA\). Das Vorzeichen sagt, ob das zugehörige Vektorpaar um den Ursprung gegen den Uhrzeigersinn oder im Uhrzeigersinn dreht.
Auch das ganze Dreieck besitzt eine orientierte Fläche, nämlich
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
Durch Ausmultiplizieren erhält man die zentrale Beziehung
$$\Delta=s_1+s_2+s_3.$$
Die drei vom Ursprung ausgeschnittenen Teilflächen addieren sich also zur orientierten Fläche von \(ABC\). Genau diese Zerlegung steckt hinter dem Test im Code.
Ein Punkt liegt genau dann strikt im Inneren eines Dreiecks, wenn alle seine baryzentrischen Koordinaten positiv sind. Für den Ursprung hat die Darstellung
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
die besonders einfache Form
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
Damit liegt \(O\) genau dann strikt in \(ABC\), wenn alle drei Quotienten positiv sind. Wegen des gemeinsamen Nenners ist das äquivalent dazu, dass \(s_1\), \(s_2\) und \(s_3\) dasselbe von null verschiedene Vorzeichen haben.
Ein Dreieck ist konvex. Eine einzige negative baryzentrische Koordinate zeigt daher schon, dass der Punkt außerhalb der gegenüberliegenden Seite liegt. In der Determinanten-Sprache bedeutet das: Sobald eines von \(s_1,s_2,s_3\) ein anderes Vorzeichen als die beiden übrigen hat, liegt der Ursprung außerhalb. Falls eine Determinante null ist, liegt \(O\) auf einer Seitenlinie und damit auf dem Rand statt im strikten Inneren.
Die entscheidende Bedingung ist also schlicht
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
Deshalb braucht die Implementierung keine Divisionen, und die gesamte Prüfung bleibt mit ganzzahliger Arithmetik exakt.
Betrachte das Dreieck
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
Dann gilt
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
Alle drei Werte sind positiv. Also sind auch die baryzentrischen Koordinaten des Ursprungs positiv, und der Ursprung liegt im Inneren dieses Dreiecks.
Zum Vergleich liefert
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
die Werte
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
Die Vorzeichen sind gemischt; also ist eine baryzentrische Koordinate negativ und der Ursprung liegt außerhalb.
Die C++-, Python- und Java-Implementierungen gehen die Dreiecksdaten zeilenweise durch, zerlegen jede Zeile in sechs ganze Zahlen und interpretieren sie als die Koordinaten von \(A\), \(B\) und \(C\). Für jedes Dreieck werden direkt die drei Determinanten \(s_1\), \(s_2\) und \(s_3\) berechnet. Eine Vorverarbeitung ist nicht nötig, weil jede Zeile unabhängig entschieden werden kann.
Die eigentliche Entscheidung ist dann nur noch ein Vorzeichentest. Die C++-Implementierung verwendet die strikte Form "alle drei positiv oder alle drei negativ" und trifft damit exakt die Bedingung für striktes Enthaltensein. Die Python- und Java-Implementierungen formulieren denselben Gedanken als "keine gemischten Vorzeichen"; außerhalb des Randfalls \(s_i=0\) ist das äquivalent. Jedes Dreieck, das den Test besteht, erhöht den Zähler um eins.
Für \(N\) Dreiecke fällt pro Dreieck nur konstanter Aufwand an: drei 2-mal-2-Determinanten und einige Vorzeichenvergleiche. Die Gesamtlaufzeit ist daher \(O(N)\).
Der geometrische Kern benötigt nur \(O(1)\) zusätzlichen Speicher. Manche Implementierungen lesen die Eingabe zunächst vollständig ein, aber mathematisch reichen das aktuelle Dreieck und der laufende Zähler. Für die Größe der Project-Euler-Eingabe ist die Berechnung praktisch sofort abgeschlossen.
Her satır, \(ABC\) üçgenini veren üç tamsayı köşe içerir. Amaç, bu üçgenlerden kaç tanesinin orijini \(O=(0,0)\) kendi iç bölgesinde barındırdığını saymaktır. Test edilen nokta her zaman aynı olduğu için bu, genel bir nokta-çokgen problemi değil; üç işaretli alana dayanan küçük bir yönelim testidir.
\(A=(x_1,y_1)\), \(B=(x_2,y_2)\), \(C=(x_3,y_3)\) olsun. Uygulamalar kayan noktalı açı hesabı, doğru kesişimi veya yinelemeli arama kullanmaz. Doğrudan orijinle kurulan üç determinantı hesaplar:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
Geometrik olarak \(s_1\), \(s_2\) ve \(s_3\), sırasıyla \(OAB\), \(OBC\) ve \(OCA\) üçgenlerinin işaretli alanlarının iki katıdır. İşaret, ilgili vektör çiftinin orijin etrafında saat yönünün tersine mi yoksa saat yönünde mi döndüğünü söyler.
Tüm üçgenin de işaretli alanı vardır:
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
Bu determinant açıldığında şu ana ilişki elde edilir:
$$\Delta=s_1+s_2+s_3.$$
Yani orijinin ayırdığı üç alt alan, yönlü olarak tam üçgenin alanına toplanır. Koddaki testin arkasındaki değişmez yapı budur.
Bir nokta, ancak ve ancak barysentrik koordinatlarının hepsi pozitifse üçgenin içinde kalır. Orijin için
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
yazımı özellikle basit hale gelir:
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
Dolayısıyla \(O\)'nun \(ABC\) içinde olması için bu üç oranın da pozitif olması gerekir. Ortak payda aynı olduğundan bu, \(s_1\), \(s_2\) ve \(s_3\)'ün sıfırdan farklı olmak üzere aynı işarete sahip olmasına eşdeğerdir.
Üçgen konveks bir şekildir. Bu nedenle tek bir negatif barysentrik koordinat bile noktanın karşı kenarın dışında olduğunu kanıtlar. Determinant dilinde bu şu anlama gelir: \(s_1,s_2,s_3\) değerlerinden biri diğer ikisinden farklı işaret taşıyorsa orijin dışarıdadır. Eğer bu değerlerden biri sıfırsa, \(O\) bir kenarın doğrusu üzerindedir; yani sınırdadır, iç bölgede değildir.
Bu yüzden belirleyici koşul sadece
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0$$
şeklindedir. Uygulamada bölme yapmaya gerek yoktur ve tamsayı aritmetiği testi tam doğrulukla yürütür.
Şu üçgeni ele alalım:
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
Burada
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345$$
olur. Üç değerin de pozitif olması, orijinin barysentrik koordinatlarının da pozitif olduğu anlamına gelir; dolayısıyla orijin bu üçgenin içindedir.
Buna karşılık
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
için
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341$$
elde edilir. İşaretler karıştığı için bir barysentrik koordinat negatiftir ve orijin dışarıda kalır.
C++, Python ve Java uygulamaları üçgen listesini satır satır işler, her satırı altı tamsayıya ayırır ve bunları \(A\), \(B\), \(C\) köşeleri olarak yorumlar. Sonra her üçgen için doğrudan \(s_1\), \(s_2\) ve \(s_3\) determinantları hesaplanır. Her satır bağımsız olduğu için ayrıca bir ön işleme gerek yoktur.
Son karar yalnızca işaret kontrolüdür. C++ uygulaması "üçü de pozitif ya da üçü de negatif" biçimindeki sıkı koşulu kullanır; bu, sıkı iç bölge tanımıyla tam olarak örtüşür. Python ve Java uygulamaları aynı fikri "karışık işaret yok" biçiminde kodlar; \(s_i=0\) sınır durumu dışında sonuç aynıdır. Testi geçen her üçgen sayaç değerini bir artırır.
\(N\) adet üçgen için her üçgende sabit miktarda işlem vardır: üç tane 2'ye 2 determinant ve birkaç işaret karşılaştırması. Bu nedenle toplam süre \(O(N)\) olur.
Geometrik çekirdek \(O(1)\) ek alan kullanır. Bazı uygulamalar giriş satırlarını önce belleğe alabilir, fakat matematiksel olarak yalnızca o anki üçgen ve biriken sayaç gerekir. Project Euler boyutlarında hesaplama pratik olarak anlıktır.
Cada fila de la entrada describe un triángulo \(ABC\) mediante tres vértices enteros. Hay que contar cuántos de esos triángulos contienen al origen \(O=(0,0)\) en su interior. Como el punto probado es siempre el mismo, no hace falta un algoritmo general de contención para polígonos; todo se reduce a un pequeño test de orientación basado en tres áreas con signo.
Sean \(A=(x_1,y_1)\), \(B=(x_2,y_2)\) y \(C=(x_3,y_3)\). Las implementaciones no usan ángulos en coma flotante, intersecciones explícitas de rectas ni búsqueda iterativa. Calculan directamente tres determinantes construidos con el origen:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
Geométricamente, \(s_1\), \(s_2\) y \(s_3\) son el doble de las áreas orientadas de \(OAB\), \(OBC\) y \(OCA\). El signo indica si cada par consecutivo de vectores gira en sentido antihorario o horario alrededor del origen.
El triángulo completo también tiene un área orientada:
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
Al expandir el determinante aparece la identidad central
$$\Delta=s_1+s_2+s_3.$$
Es decir, las tres subáreas determinadas por el origen suman el área orientada de \(ABC\). Esa descomposición es el invariante geométrico que hace funcionar el criterio de signos.
Un punto está estrictamente dentro de un triángulo si y solo si sus coordenadas baricéntricas son todas positivas. Para el origen, la representación
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
adopta la forma cerrada
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
Por tanto, \(O\) está estrictamente dentro de \(ABC\) exactamente cuando esos tres cocientes son positivos. Como el denominador es común, eso equivale a que \(s_1\), \(s_2\) y \(s_3\) tengan el mismo signo distinto de cero.
Un triángulo es convexo. Por eso, una sola coordenada baricéntrica negativa ya demuestra que el punto quedó fuera del lado opuesto al vértice correspondiente. En términos de los determinantes, si uno de \(s_1,s_2,s_3\) tiene signo opuesto a los otros dos, el origen está fuera. Si alguno vale cero, entonces \(O\) es colineal con uno de los lados y cae sobre la frontera, no en el interior estricto.
La condición decisiva es simplemente
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
Así se evita cualquier división en el código y la aritmética entera mantiene la prueba exacta.
Consideremos el triángulo
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
Entonces
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
Los tres valores son positivos, así que las tres coordenadas baricéntricas del origen también lo son. Por tanto, el origen está dentro de ese triángulo.
En cambio, para
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
obtenemos
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
Como los signos están mezclados, una coordenada baricéntrica es negativa y el origen queda fuera.
Las implementaciones en C++, Python y Java recorren la lista de triángulos fila por fila, separan cada fila en seis enteros y los interpretan como las coordenadas de \(A\), \(B\) y \(C\). Para cada triángulo calculan directamente los tres determinantes \(s_1\), \(s_2\) y \(s_3\). No existe fase de preprocesamiento porque cada caso se decide de manera independiente.
La decisión final es un test de signos. La implementación en C++ usa la forma estricta "los tres positivos o los tres negativos", que coincide exactamente con la contención estricta. Las implementaciones en Python y Java expresan la misma idea como "sin signos mezclados"; salvo en el caso frontera \(s_i=0\), ambos criterios coinciden. Cada triángulo que supera el test incrementa el contador acumulado.
Si hay \(N\) triángulos, el algoritmo realiza una cantidad constante de trabajo por triángulo: tres determinantes \(2\times2\) y unas pocas comparaciones de signo. El tiempo total es, por tanto, \(O(N)\).
El núcleo geométrico usa \(O(1)\) espacio adicional. Algunas implementaciones pueden conservar todas las líneas de entrada antes de procesarlas, pero matemáticamente solo hacen falta el triángulo actual y el contador. Para el tamaño de la entrada de Project Euler, el cálculo es prácticamente instantáneo.
输入中的每一行都给出一个三角形 \(ABC\) 的三个整数顶点。任务是统计这些三角形中，有多少个把原点 \(O=(0,0)\) 严格包含在内部。由于被测试的点始终固定为原点，这个问题不需要一般性的点在多边形内算法；它会退化成一个只涉及三个带符号面积的方向判定。
设 \(A=(x_1,y_1)\)、\(B=(x_2,y_2)\)、\(C=(x_3,y_3)\)。实现中没有使用浮点角度、直线求交或迭代搜索，而是直接计算与原点相关的三个行列式：
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
从几何上看，\(s_1\)、\(s_2\)、\(s_3\)分别是三角形 \(OAB\)、\(OBC\)、\(OCA\) 的有向面积的两倍。它们的符号记录了相邻两个顶点向量绕原点转动时是逆时针还是顺时针。
整个三角形 \(ABC\) 也有一个有向面积：
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
把这个行列式展开以后，会得到核心恒等式
$$\Delta=s_1+s_2+s_3.$$
也就是说，以原点为公共顶点切出的三个有向子面积，恰好加起来就是三角形 \(ABC\) 的有向面积。代码中的判定本质上正是利用了这一结构不变量。
一个点严格位于三角形内部，当且仅当它的重心坐标全部为正。对原点来说，表示式
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
可以直接化成
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
因此，\(O\) 严格位于 \(ABC\) 内部，当且仅当这三个比值都为正。由于分母相同，这又等价于 \(s_1\)、\(s_2\)、\(s_3\) 具有相同且非零的符号。
三角形是凸集，所以只要有一个重心坐标为负，就说明该点落在对应对边的外侧。翻译成行列式语言，就是说只要 \(s_1,s_2,s_3\) 中有一个与另外两个符号不同，原点就在三角形外部。如果其中某个值恰好为零，则原点与某一条边共线，这时原点位于边界而不是严格内部。
因此，决定性的条件就是
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
实现时完全不需要做除法，而且整数运算能保证判定没有浮点误差。
先看三角形
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
此时
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
三个值全部为正，所以原点的三个重心坐标也都为正，原点就在这个三角形内部。
再看
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
得到
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
符号出现了分裂，因此必有一个重心坐标为负，原点就在三角形外部。
C++、Python 和 Java 实现都会逐行读取三角形数据，把每一行拆成六个整数，并把它们解释为 \(A\)、\(B\)、\(C\) 的坐标。随后直接计算上面的三个行列式 \(s_1\)、\(s_2\)、\(s_3\)。由于每个三角形都可以独立判定，所以不存在额外的预处理阶段。
最后一步只是符号判断。C++ 实现使用严格版本，即"三个都为正"或"三个都为负"，这与严格包含完全一致。Python 和 Java 实现则写成"不能同时出现正号和负号"；只要没有边界情形 \(s_i=0\)，两种写法就是同一个几何条件。每通过一次判定，计数器加一，最终计数器就是答案。
如果共有 \(N\) 个三角形，那么每个三角形只需要常数次运算：三个 \(2\times2\) 行列式和若干符号比较，因此总时间复杂度为 \(O(N)\)。
几何判定本身只需要 \(O(1)\) 额外空间。有些实现可能会先把输入行全部读入内存，但从数学核心来看，只需要当前三角形和累计计数。对于 Project Euler 的输入规模，这个计算几乎是瞬间完成的。
Каждая строка входных данных задает один треугольник \(ABC\) тремя целочисленными вершинами. Нужно посчитать, сколько таких треугольников содержат начало координат \(O=(0,0)\) строго внутри. Поскольку проверяемая точка фиксирована, здесь не нужен общий алгоритм для произвольного многоугольника: задача сводится к короткому тесту ориентации через три знаковые площади.
Пусть \(A=(x_1,y_1)\), \(B=(x_2,y_2)\), \(C=(x_3,y_3)\). Реализации не используют вещественные углы, явные пересечения прямых или какой-либо перебор. Они сразу вычисляют три определителя, построенные относительно начала координат:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
Геометрически \(s_1\), \(s_2\) и \(s_3\) равны удвоенным ориентированным площадям треугольников \(OAB\), \(OBC\) и \(OCA\). Их знак показывает, происходит ли поворот соответствующей пары векторов вокруг начала координат против часовой стрелки или по часовой стрелке.
У всего треугольника \(ABC\) тоже есть ориентированная площадь:
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
После раскрытия определителя получается ключевое равенство
$$\Delta=s_1+s_2+s_3.$$
То есть три ориентированные под-площади, образованные началом координат, в сумме дают ориентированную площадь \(ABC\). Именно это разложение лежит в основе критерия, используемого в коде.
Точка лежит строго внутри треугольника тогда и только тогда, когда все ее барицентрические координаты положительны. Для начала координат представление
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
упрощается до формул
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
Следовательно, \(O\) лежит строго внутри \(ABC\) тогда и только тогда, когда все три дроби положительны. Поскольку знаменатель общий, это эквивалентно тому, что \(s_1\), \(s_2\) и \(s_3\) имеют один и тот же ненулевой знак.
Треугольник выпуклый, поэтому одна отрицательная барицентрическая координата уже означает, что точка находится по внешнюю сторону от противоположного ребра. В языке определителей это означает: если один из \(s_1,s_2,s_3\) имеет знак, отличный от двух других, начало координат находится вне треугольника. Если же какой-то определитель равен нулю, то \(O\) коллинеарна одной из сторон и лежит на границе, а не строго внутри.
Поэтому решающее условие выглядит так:
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
В реализации не нужны деления, а целочисленная арифметика делает тест точным.
Рассмотрим треугольник
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
Тогда
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
Все три числа положительны, значит и все барицентрические координаты начала координат положительны. Следовательно, начало координат находится внутри этого треугольника.
Для сравнения, если взять
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645),$$
то получаем
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
Знаки смешаны, поэтому одна барицентрическая координата отрицательна и начало координат лежит вне треугольника.
Реализации на C++, Python и Java проходят по списку треугольников построчно, разбивают каждую строку на шесть целых чисел и интерпретируют их как координаты \(A\), \(B\) и \(C\). Для каждого треугольника сразу вычисляются три определителя \(s_1\), \(s_2\) и \(s_3\). Предварительная обработка не нужна, потому что каждый случай решается независимо.
Итоговое решение сводится к проверке знаков. Реализация на C++ использует строгую форму "все три положительны или все три отрицательны", что точно совпадает с понятием строгого попадания внутрь. Реализации на Python и Java записывают ту же идею как "нет смешанных знаков"; вне граничного случая \(s_i=0\) это эквивалентно. Каждый треугольник, прошедший тест, увеличивает счетчик на единицу.
Если всего \(N\) треугольников, то на каждый требуется постоянное число операций: три определителя \(2\times2\) и несколько сравнений знаков. Значит, полное время работы равно \(O(N)\).
Сам геометрический тест требует \(O(1)\) дополнительной памяти. Некоторые реализации могут сначала сохранить все строки ввода, но математическому ядру нужны только текущий треугольник и накопленный счетчик. Для размера входа в Project Euler вычисление выполняется практически мгновенно.
كل سطر في الإدخال يصف مثلثًا \(ABC\) عبر ثلاثة رؤوس صحيحة الإحداثيات. المطلوب هو عدّ عدد المثلثات التي تحتوي نقطة الأصل \(O=(0,0)\) في داخلها الداخلي الصارم. وبما أن النقطة المختبرة ثابتة دائمًا، فالمسألة ليست اختبار احتواء عام لنقطة داخل مضلع، بل تختزل إلى فحص اتجاه صغير يعتمد على ثلاث مساحات موقعة.
لنكتب \(A=(x_1,y_1)\)، و\(B=(x_2,y_2)\)، و\(C=(x_3,y_3)\). لا تستخدم التطبيقات زوايا عائمة أو حساب تقاطع مستقيمين أو أي بحث تكراري. بدلًا من ذلك تحسب مباشرة ثلاثة محددات بالنسبة إلى الأصل:
$$s_1=x_1y_2-y_1x_2,\qquad s_2=x_2y_3-y_2x_3,\qquad s_3=x_3y_1-y_3x_1.$$
هندسيًا تمثل \(s_1\) و\(s_2\) و\(s_3\) ضعفي المساحات الموجهة للمثلثات \(OAB\) و\(OBC\) و\(OCA\). وتحدد إشارة كل قيمة ما إذا كان الدوران بين متجهين متتاليين حول الأصل يتم عكس عقارب الساعة أو مع عقارب الساعة.
للمثلث الكامل \(ABC\) أيضًا مساحة موجهة مقدارها
$$\Delta=\det(B-A,C-A)=x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2).$$
وبتوسيع هذا المحدد نحصل على العلاقة الأساسية
$$\Delta=s_1+s_2+s_3.$$
أي إن المساحات الثلاث الجزئية التي يحددها الأصل تتجمع لتعطي المساحة الموجهة للمثلث \(ABC\). وهذه هي البنية الثابتة التي يقوم عليها اختبار الاحتواء.
تقع النقطة داخل المثلث تمامًا إذا كانت جميع إحداثياتها الباريцентрية موجبة. وبالنسبة إلى الأصل فإن التمثيل
$$O=\lambda_1A+\lambda_2B+\lambda_3C,\qquad \lambda_1+\lambda_2+\lambda_3=1$$
يتحول إلى الصيغة المباشرة
$$\lambda_1=\frac{s_2}{\Delta},\qquad \lambda_2=\frac{s_3}{\Delta},\qquad \lambda_3=\frac{s_1}{\Delta}.$$
إذن تكون \(O\) داخل \(ABC\) داخليًا وبصورة صارمة إذا وفقط إذا كانت هذه الكسور الثلاثة موجبة. وبما أن المقام واحد، فهذا يكافئ أن تكون \(s_1\) و\(s_2\) و\(s_3\) جميعًا ذات الإشارة نفسها وغير صفرية.
المثلث شكل محدب، ولذلك فإن وجود إحداثي باريцентري سالب واحد يكفي لإثبات أن النقطة تقع خارج الضلع المقابل للرأس الموافق. بلغة المحددات، إذا كانت إحدى القيم \(s_1,s_2,s_3\) ذات إشارة مخالفة للقيمتين الأخريين، فالأصل خارج المثلث. وإذا كانت إحدى هذه القيم صفرًا، فإن \(O\) تقع على استقامة أحد الأضلاع، أي على الحدود لا في الداخل الصارم.
ولهذا فشرط الحسم هو ببساطة
$$s_1,s_2,s_3 \gt 0\quad\text{or}\quad s_1,s_2,s_3 \lt 0.$$
ولا حاجة في التنفيذ إلى أي قسمة، كما أن الحساب الصحيح بالكامل يحافظ على الدقة من دون أخطاء عددية عائمة.
لنأخذ المثلث
$$A=(-340,495),\qquad B=(-153,-910),\qquad C=(835,-947).$$
فنحصل على
$$s_1=385135,\qquad s_2=904741,\qquad s_3=91345.$$
جميع القيم موجبة، وبالتالي تكون جميع الإحداثيات الباريцентрية لنقطة الأصل موجبة أيضًا، ومن ثم فالأصل داخل هذا المثلث.
أما إذا أخذنا
$$A=(-175,41),\qquad B=(-421,-714),\qquad C=(574,-645)$$
فإننا نجد
$$s_1=142211,\qquad s_2=681381,\qquad s_3=-89341.$$
الإشارات هنا مختلطة، وهذا يعني أن أحد الإحداثيات الباريцентрية سالب وأن الأصل يقع خارج المثلث.
تقرأ تطبيقات C++ وPython وJava قائمة المثلثات سطرًا سطرًا، ثم تقسّم كل سطر إلى ستة أعداد صحيحة وتفسرها على أنها إحداثيات \(A\) و\(B\) و\(C\). بعد ذلك تحسب مباشرة المحددات الثلاثة \(s_1\) و\(s_2\) و\(s_3\). ولا توجد مرحلة تمهيدية لأن كل مثلث يمكن الحكم عليه بصورة مستقلة.
القرار النهائي هو مجرد فحص للإشارات. تستخدم نسخة C++ الصيغة الصارمة: "القيم الثلاث كلها موجبة أو كلها سالبة"، وهي مطابقة تمامًا لفكرة الاحتواء الداخلي الصارم. أما نسختا Python وJava فتصوغان الفكرة نفسها على شكل "لا توجد إشارات متضادة"، وهو شرط مكافئ ما لم تظهر حالة حدية من النوع \(s_i=0\). وكل مثلث يجتاز الاختبار يزيد العداد بمقدار واحد.
إذا كان عدد المثلثات هو \(N\)، فإن العمل المطلوب لكل مثلث ثابت: ثلاثة محددات \(2\times2\) وبعض مقارنات الإشارة. لذلك يكون زمن التنفيذ الكلي \(O(N)\).
أما الذاكرة الإضافية التي يحتاجها لب الاختبار الهندسي فهي \(O(1)\). قد تحتفظ بعض التطبيقات بكل سطور الإدخال قبل المعالجة، لكن الجوهر الرياضي لا يحتاج إلا إلى المثلث الحالي والعداد التراكمي. وبالنسبة إلى حجم إدخال Project Euler، فإن الحساب يتم عمليًا بشكل فوري.