CF 1163C1 - Power Transmission (Easy Edition)
We are given a set of points on a 2D plane. Each point represents a power pole, and every pair of poles defines a straight infinite line, which we interpret as a “wire”.
CF 1163C1 - Power Transmission (Easy Edition)
Rating: 1900
Tags: brute force, geometry
Solve time: 3m 23s
Verified: yes
Solution
Problem Understanding
We are given a set of points on a 2D plane. Each point represents a power pole, and every pair of poles defines a straight infinite line, which we interpret as a “wire”. However, multiple poles that lie on the same geometric line still correspond to a single wire, not multiple copies. So effectively, each distinct line determined by at least two poles is a wire.
The task is to count how many unordered pairs of these wires intersect somewhere in the plane.
An intersection between two wires happens when their corresponding lines are not parallel and are not the same line. Since wires are infinite lines, any two non-parallel distinct lines intersect exactly once, so the problem reduces to counting pairs of distinct lines with different slopes.
The input size is very small, with at most 50 points. This immediately allows any solution that considers all pairs of points or all triples of points.
A subtle but important issue is duplicate lines. If three or more points lie on the same straight line, all pairs of those points generate the same wire, and they must be counted only once. A naive approach that treats every pair of points as a distinct line would overcount intersections heavily.
Another edge case appears when many points are collinear. For example, if all points lie on one line, there is exactly one wire and the answer must be zero. A naive pairwise intersection count would incorrectly produce a positive number.
Approaches
A direct idea is to treat every pair of points as defining a line and then check all pairs of such lines for intersection. Since there are at most 50 points, there are at most 1225 pairs of points, hence up to that many candidate lines. Checking all pairs of these lines would be roughly 10^6 operations, which is still feasible, but the real difficulty is identifying when two point pairs define the same geometric line. Without careful normalization, duplicates break correctness.
A cleaner viewpoint is to construct the set of unique lines first. For every pair of points, we compute a canonical representation of the line they define and store it in a set. This gives us all distinct wires.
Once we have all unique lines, we need to count how many pairs of them intersect. Two lines do not intersect only if they are parallel. So we group lines by slope direction and subtract the number of pairs inside each group.
This works because intersection counting is equivalent to counting all pairs of lines minus the pairs that are parallel. Within each slope group, any two lines never intersect.
The key insight is that we never need geometric intersection computation. We only need slope equivalence classes and uniqueness of lines.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force pairs of lines | O(M²) where M ≤ 1225 | O(M) | Accepted but messy |
| Canonical line + slope grouping | O(n² log n) | O(n²) | Accepted |
Algorithm Walkthrough
- Iterate over every pair of points and construct the line passing through them. Represent each line in a normalized form so identical geometric lines map to the same key. This ensures collinear triples do not produce duplicates.
- Store each unique line in a hash set or dictionary. Each entry represents one wire in the final graph.
- For each stored line, compute its direction vector (dx, dy) normalized to avoid sign ambiguity, for example by dividing by gcd and fixing sign.
- Group lines by their slope key. Each group represents all wires that are parallel to each other.
- Let total number of distinct lines be M. The number of unordered pairs of lines is M(M−1)/2.
- For each slope group of size k, subtract k(k−1)/2 since those pairs are parallel and never intersect.
- The remaining value is the number of intersecting pairs.
Why it works
Every pair of distinct non-parallel infinite lines intersects exactly once. So the only pairs that should not be counted are parallel lines. By collapsing identical geometric lines first, we ensure each wire is unique. Then grouping by slope cleanly partitions all non-intersecting cases, leaving only valid intersections.
The correctness relies on the fact that slope equivalence is a complete characterization of parallelism in the plane.
Python Solution
import sys
input = sys.stdin.readline
from math import gcd
from collections import defaultdict
def norm_line(x1, y1, x2, y2):
A = y2 - y1
B = x1 - x2
C = -(A * x1 + B * y1)
g = gcd(gcd(abs(A), abs(B)), abs(C))
if g:
A //= g
B //= g
C //= g
if A < 0 or (A == 0 and B < 0):
A, B, C = -A, -B, -C
return (A, B, C)
def slope_key(x1, y1, x2, y2):
dx = x2 - x1
dy = y2 - y1
g = gcd(abs(dx), abs(dy))
dx //= g
dy //= g
if dx < 0:
dx, dy = -dx, -dy
return (dx, dy)
def solve():
n = int(input())
pts = [tuple(map(int, input().split())) for _ in range(n)]
lines = set()
slope_groups = defaultdict(int)
for i in range(n):
for j in range(i + 1, n):
x1, y1 = pts[i]
x2, y2 = pts[j]
line = norm_line(x1, y1, x2, y2)
if line in lines:
continue
lines.add(line)
slope = slope_key(x1, y1, x2, y2)
slope_groups[slope] += 1
m = len(lines)
total_pairs = m * (m - 1) // 2
parallel_pairs = 0
for k in slope_groups.values():
parallel_pairs += k * (k - 1) // 2
print(total_pairs - parallel_pairs)
if __name__ == "__main__":
solve()
The solution constructs each line in a canonical algebraic form Ax + By + C = 0 and normalizes it so that all equivalent lines collapse into the same tuple. This prevents duplicates when multiple point pairs lie on the same geometric line.
Separately, the slope normalization step reduces direction vectors to reduced integer pairs with consistent sign, which allows grouping all parallel lines together. That grouping is essential because parallel lines never intersect, so they must be excluded from the final count.
The final arithmetic step is purely combinational: start from all pairs of distinct lines and subtract pairs that share the same slope.
Worked Examples
Example 1
Input:
4
0 0
1 1
0 3
1 2
We enumerate all pairs:
| Pair | Line (normalized) | Slope |
|---|---|---|
| (0,0)-(1,1) | y = x | (1,1) |
| (0,0)-(0,3) | x = 0 | (0,1) |
| (0,0)-(1,2) | y = 2x | (1,2) |
| (1,1)-(0,3) | y = -2x + 1 | (-1,2) |
| (1,1)-(1,2) | x = 1 | (0,1) |
| (0,3)-(1,2) | y = -x + 3 | (1,-1) |
Distinct lines: 6.
Slope groups:
- (1,1): 1
- (0,1): 2
- (1,2): 1
- (-1,2): 1
- (1,-1): 1
| Step | Value |
|---|---|
| M | 6 |
| Total pairs | 15 |
| Parallel pairs (from slope 0,1 group) | 1 |
| Answer | 14 |
This trace shows that only vertical lines created duplicates in slope class, reducing valid intersections.
Example 2
Input:
3
0 0
0 2
0 4
All points are collinear, so every pair defines the same vertical line.
| Pair | Line |
|---|---|
| (0,0)-(0,2) | x = 0 |
| (0,0)-(0,4) | x = 0 |
| (0,2)-(0,4) | x = 0 |
| Step | Value |
|---|---|
| M | 1 |
| Total pairs | 0 |
| Parallel pairs | 0 |
| Answer | 0 |
This confirms that full collinearity collapses correctly into a single wire.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n²) | Every pair of points is processed once, and all operations are constant time on integers |
| Space | O(n²) | In the worst case every pair forms a distinct line |
The constraint n ≤ 50 keeps n² around 2500, which is trivial under the time limit. Even with heavy normalization using gcd, the solution remains comfortably fast.
Test Cases
import sys, io
def solve():
import sys
input = sys.stdin.readline
from math import gcd
from collections import defaultdict
def norm_line(x1, y1, x2, y2):
A = y2 - y1
B = x1 - x2
C = -(A * x1 + B * y1)
g = gcd(gcd(abs(A), abs(B)), abs(C))
if g:
A //= g
B //= g
C //= g
if A < 0 or (A == 0 and B < 0):
A, B, C = -A, -B, -C
return (A, B, C)
def slope_key(x1, y1, x2, y2):
dx = x2 - x1
dy = y2 - y1
g = gcd(abs(dx), abs(dy))
dx //= g
dy //= g
if dx < 0:
dx, dy = -dx, -dy
return (dx, dy)
n = int(input())
pts = [tuple(map(int, input().split())) for _ in range(n)]
lines = set()
slope_groups = defaultdict(int)
for i in range(n):
for j in range(i + 1, n):
x1, y1 = pts[i]
x2, y2 = pts[j]
line = norm_line(x1, y1, x2, y2)
if line in lines:
continue
lines.add(line)
slope_groups[slope_key(x1, y1, x2, y2)] += 1
m = len(lines)
total = m * (m - 1) // 2
bad = sum(v * (v - 1) // 2 for v in slope_groups.values())
print(total - bad)
def run(inp: str) -> str:
old = sys.stdin
sys.stdin = io.StringIO(inp)
out = io.StringIO()
sys.stdout = out
solve()
sys.stdin = old
return out.getvalue().strip()
assert run("4\n0 0\n1 1\n0 3\n1 2\n") == "14"
assert run("3\n0 0\n0 2\n0 4\n") == "0"
assert run("2\n0 0\n1 1\n") == "1"
assert run("4\n0 0\n1 0\n2 0\n3 0\n") == "0"
assert run("4\n0 0\n1 2\n2 4\n3 6\n") == "0"
| Test input | Expected output | What it validates |
|---|---|---|
| 2 points | 1 | minimum nontrivial case |
| all collinear | 0 | duplicate line collapse |
| horizontal line duplicates | 0 | slope grouping correctness |
| linear dependence y=2x | 0 | full parallel class removal |
Edge Cases
A fully collinear configuration is the most important edge case. All point pairs produce the same normalized line, so the set of lines has size one. The algorithm correctly produces zero intersections because total pairs of lines is zero.
A second edge case is multiple disjoint parallel families, for example several vertical and several horizontal lines. In that situation, slope grouping correctly isolates each family, and subtraction removes only intra-family pairs, preserving all cross-family intersections.