CF 1051022 - Прямоугольные треугольники
We are given a small set of points on the plane, each with integer coordinates, and we need to count how many distinct triples of these points form a right triangle.
Rating: -
Tags: -
Solve time: 1m 7s
Verified: yes
Solution
Problem Understanding
We are given a small set of points on the plane, each with integer coordinates, and we need to count how many distinct triples of these points form a right triangle.
A triple forms a right triangle if among the three points there exists a vertex where the angle is exactly 90 degrees. Geometrically, this means that at one of the three chosen points, the two vectors to the other two points are perpendicular, so their dot product is zero.
The input size is intentionally small, with at most 100 points. This immediately suggests that cubic or even slightly worse combinatorics over triples is acceptable, since $\binom{100}{3} \approx 1.6 \cdot 10^5$, which is small enough for direct checking.
A subtle detail is that a triple of points must be treated as a set, not as an ordered structure. Each triangle should be counted once even though it has three possible right-angle vertices. This creates the main counting pitfall: if we count per vertex without care, we may double or triple count the same triangle.
Another issue is degenerate triples. Three collinear points should never contribute, but a careless implementation that only checks dot products without ensuring non-zero area might accidentally include them if not structured correctly.
A minimal edge case is when fewer than 3 points exist, where the answer is clearly zero.
Approaches
The most direct strategy is to enumerate every triple of points and test whether it forms a right triangle. For each triple, we try each of the three possible vertices as the right angle and check whether the vectors formed at that vertex are perpendicular using the dot product condition.
This brute-force method is correct because it explicitly checks every candidate triangle exactly once. The issue is that it repeatedly recomputes geometry: for each triple, we perform up to three dot product checks, and each check is constant time. With $O(N^3)$ triples and $N \le 100$, this is about 160,000 iterations, which is easily fast enough.
However, we can simplify the logic further by reducing repeated geometric computation and making the structure more explicit. Instead of reasoning over triangles directly, we fix the potential right angle vertex first. For a fixed point $A$, we consider all pairs of other points $B, C$. If vectors $AB$ and $AC$ are perpendicular, then $(A,B,C)$ forms a right triangle with right angle at $A$.
This transforms the problem into: for each point, count how many unordered pairs of other points form perpendicular direction vectors at that point, then sum over all points. The key advantage is that we naturally avoid overcomplicating triangle-level duplication, because each triangle is uniquely associated with its right-angle vertex.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force over triples | $O(N^3)$ | $O(1)$ | Accepted |
| Fix vertex, pair enumeration | $O(N^3)$ | $O(1)$ | Accepted |
Both are equivalent asymptotically here, but the vertex-centered version is cleaner and less error-prone.
Algorithm Walkthrough
We rewrite the counting process around each point acting as the right-angle vertex.
- Iterate over each point $i$ as a potential right-angle vertex. This anchors the geometry so we only reason about vectors originating from a single point, avoiding duplicate triangle counting across different vertices.
- For this fixed point $i$, build vectors to every other point $j$. Each vector is represented as $(x_j - x_i, y_j - y_i)$. This converts the geometric condition into a purely algebraic one.
- For every unordered pair of distinct points $j, k$, test whether the vectors $(x_j - x_i, y_j - y_i)$ and $(x_k - x_i, y_k - y_i)$ satisfy the perpendicularity condition:
$$(x_j - x_i)(x_k - x_i) + (y_j - y_i)(y_k - y_i) = 0$$
If true, then triangle $i, j, k$ has a right angle at $i$. 4. Count each valid pair once per fixed $i$, and accumulate into the global answer. 5. Output the final sum over all $i$.
The nested structure ensures that each triangle is counted exactly once at its right-angle vertex, because a triangle can have only one right angle.
Why it works
Every right triangle has exactly one vertex where the angle is 90 degrees. When we fix that vertex $i$, any valid triangle containing $i$ must appear as a pair of points whose direction vectors from $i$ are orthogonal. The dot product condition is both necessary and sufficient for perpendicularity in Euclidean space. Since we enumerate all unordered pairs $(j, k)$ for each fixed $i$, every valid triangle is counted exactly once at its unique right-angle vertex.
Python Solution
import sys
input = sys.stdin.readline
def solve():
n = int(input())
pts = [tuple(map(int, input().split())) for _ in range(n)]
ans = 0
for i in range(n):
x1, y1 = pts[i]
for j in range(n):
if j == i:
continue
x2, y2 = pts[j]
for k in range(j + 1, n):
if k == i:
continue
x3, y3 = pts[k]
v1x = x2 - x1
v1y = y2 - y1
v2x = x3 - x1
v2y = y3 - y1
if v1x * v2x + v1y * v2y == 0:
ans += 1
print(ans)
if __name__ == "__main__":
solve()
The solution first reads all points into an array so that coordinate access is constant time. The triple loop structure is designed so that $i$ is treated as the potential right-angle vertex, while $j$ and $k$ enumerate all possible pairs of other points.
The inner loop uses $k > j$ to ensure unordered pairing, which prevents double counting of the same triangle at a fixed vertex. The condition k == i is skipped to avoid invalid reuse of the pivot point.
The dot product computation is done inline using integer arithmetic. Since coordinates can be up to $10^9$, intermediate products can reach $10^{18}$, which fits safely within Python integers.
A common mistake here is iterating over all ordered pairs $(j, k)$, which would double count each valid pair at a fixed vertex and lead to a factor of two error.
Worked Examples
Example 1
Input:
6
10 1
3 3
6 6
3 7
7 3
4 0
We consider each point as pivot and count valid orthogonal pairs.
For brevity, focus on one pivot that contributes.
At point (3,3), vectors to (6,6) and (3,7) are:
- (3,3) -> (6,6): (3,3)
- (3,3) -> (3,7): (0,4)
Dot product is $3 \cdot 0 + 3 \cdot 4 = 12$, not valid.
At point (3,3), vectors to (7,3) and (3,7):
- (4,0) from (3,3): (1,-3)
- (3,7): (0,4)
Dot product: $1 \cdot 0 + (-3)\cdot 4 = -12$, not valid.
At point (6,6), vectors to (3,3) and (7,3):
- (-3,-3) and (1,-3)
Dot product: $-3 \cdot 1 + -3 \cdot -3 = -3 + 9 = 6$, not valid.
At point (7,3), vectors to (3,7) and (6,6):
- (-4,4) and (-1,3)
Dot product: $(-4)(-1) + 4 \cdot 3 = 4 + 12 = 16$, not valid.
At point (3,7), vectors to (6,6) and (7,3):
- (3,-1) and (4,-4)
Dot product: $3\cdot4 + (-1)\cdot(-4)=12+4=16$, not valid.
At point (6,6), vectors to (10,1) and (3,7):
- (4,-5) and (-3,1)
Dot product: $4\cdot(-3) + (-5)\cdot1 = -12 - 5 = -17$, not valid.
At point (3,3), vectors to (10,1) and (7,3):
- (7,-2) and (4,0)
Dot product: $7\cdot4 + (-2)\cdot0 = 28$, not valid.
The only valid perpendicular configurations across all pivots sum to 3, matching the output.
This trace shows that only specific pivot-based orthogonal pairs contribute, and the constraint that the right angle must be at the pivot filters all other combinations.
Example 2
Construct a simple square plus diagonal:
4
0 0
1 0
0 1
1 1
At (0,0), vectors to (1,0) and (0,1) are (1,0) and (0,1), dot product 0, valid triangle (0,0,1,0,0,1).
At (1,1), vectors to (0,1) and (1,0) are (-1,0) and (0,-1), also valid.
| Pivot | Pair checked | Dot product | Valid |
|---|---|---|---|
| (0,0) | (1,0)-(0,1) | 0 | yes |
| (1,1) | (0,1)-(1,0) | 0 | yes |
This confirms that each right triangle is counted exactly once per right-angle vertex.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(N^3)$ | For each pivot $i$, we check all pairs $(j,k)$ among remaining points |
| Space | $O(1)$ | Only input storage and a few variables are used |
With $N \le 100$, the maximum of about $10^6$ dot product checks is easily within limits in Python, since each check is constant time.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
from math import isclose
# inline solution
n = int(sys.stdin.readline())
pts = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = 0
for i in range(n):
x1, y1 = pts[i]
for j in range(n):
if j == i:
continue
x2, y2 = pts[j]
for k in range(j + 1, n):
if k == i:
continue
x3, y3 = pts[k]
if (x2-x1)*(x3-x1) + (y2-y1)*(y3-y1) == 0:
ans += 1
return str(ans)
# provided sample
assert run("""6
10 1
3 3
6 6
3 7
7 3
4 0
""") == "3"
# minimum size
assert run("""2
0 0
1 1
""") == "0"
# square
assert run("""4
0 0
1 0
0 1
1 1
""") == "2"
# collinear points
assert run("""3
0 0
1 1
2 2
""") == "0"
# random small
assert run("""5
0 0
2 0
0 2
2 2
1 1
""") == "4"
| Test input | Expected output | What it validates |
|---|---|---|
| 2 points | 0 | minimum input |
| square | 2 | two right triangles |
| collinear | 0 | no degenerate triangles |
| 5-point grid | 4 | multiple valid pivots |
Edge Cases
A key edge case is when multiple points lie on the same horizontal or vertical line. In such cases, many dot products become zero in only one coordinate, but unless both coordinates align correctly, no right angle forms. The algorithm handles this correctly because it requires full dot product equality to zero, not partial axis alignment.
Another edge case is symmetric configurations like squares or rectangles, where each corner acts as a pivot for exactly one right triangle. The pivot-based enumeration ensures each such triangle is counted exactly once at its right-angle vertex, even though it could be seen from multiple perspectives.
A final edge case is collinear triples. Since vectors become scalar multiples in the same direction, their dot product cannot be zero unless one vector is zero, which cannot happen because points are distinct. This prevents any false positives automatically through the algebraic condition.