CF 104279J - 数矩形

Rating: -
Tags: -
Solve time: 47s
Verified: yes

Solution

Problem Understanding

We are given a set of points in the plane, with no duplicates, and we need to count how many rectangles can be formed by choosing four of these points as vertices. The key geometric condition is that rectangles are allowed to have any orientation, not just axis-aligned ones, so we are looking for arbitrary Euclidean rectangles formed by subsets of the points.

A rectangle in the plane is completely determined by its two diagonally opposite vertices. If we fix two points as candidates for opposite corners, they define a segment that would be a diagonal of a rectangle. The remaining two vertices must lie such that all four points form equal diagonals and right angles, which implies strong symmetry constraints.

The input size n is at most 1000. A naive O(n^4) enumeration of quadruples is far too slow because it would check on the order of 10^12 combinations in the worst case. Even O(n^3) approaches are borderline, but O(n^2 log n) or O(n^2) solutions are acceptable.

A subtle issue is overcounting. Each rectangle has two diagonals, and if we are not careful, the same rectangle will be counted multiple times depending on which diagonal pair we choose.

There are no special pathological constraints like collinearity restrictions, but degeneracy concerns matter: any method relying on slopes must handle vertical lines, floating precision, or normalization carefully. Integer geometry is preferable.

Approaches

The brute-force idea is to try every quadruple of points and check whether they form a rectangle. For four points, we could verify that all pairwise distances match the rectangle structure or that vectors between edges are perpendicular. This is conceptually simple: compute distances or dot products and test the rectangle conditions.

However, this approach scales poorly. There are about n^4 / 24 quadruples, which at n = 1000 is on the order of 10^11 checks, each requiring constant work. Even with very fast arithmetic, this is infeasible.

The key structural observation is that every rectangle has two diagonally opposite corners whose midpoint is the same. If we take any pair of points as potential diagonal endpoints, that pair uniquely determines a midpoint and a squared diagonal length. For a valid rectangle, there must be another distinct pair of points that shares the same midpoint and the same diagonal length. Those two pairs together form exactly one rectangle.

This reduces the problem from searching quadruples to grouping pairs of points. Each pair contributes a signature consisting of its midpoint and squared distance. Counting how many rectangles correspond to repeated signatures becomes a frequency counting problem over all O(n^2) pairs.

If a particular signature appears k times, meaning k distinct pairs share the same midpoint and diagonal length, then each rectangle corresponds to choosing two of those pairs. Thus the number of rectangles contributed by this group is C(k, 2).

Approach	Time Complexity	Space Complexity	Verdict
Brute Force over quadruples	O(n^4)	O(1)	Too slow
Pair grouping by midpoint and distance	O(n^2 log n) or O(n^2)	O(n^2)	Accepted

Algorithm Walkthrough

We will convert each pair of points into a canonical representation of a potential rectangle diagonal, then count how often each representation appears.

Iterate over all unordered pairs of points (i, j). For each pair, compute the midpoint of segment ij, but to avoid floating-point arithmetic, represent it as the doubled midpoint (xi + xj, yi + yj). This avoids division entirely and preserves uniqueness.
Compute the squared distance between the two points: dx^2 + dy^2. This ensures that pairs with the same diagonal length are grouped correctly without using square roots.
Combine these two values into a single key. This key represents a potential rectangle diagonal class. Two different diagonals of the same rectangle will always have identical midpoint and identical squared length, so they map to the same key.
Use a hash map to count how many pairs produce each key.
After processing all pairs, iterate over all keys. For each frequency k, add k * (k - 1) / 2 to the answer. This counts how many ways we can choose two diagonals that form a rectangle.
Output the accumulated sum.

Why it works

Every rectangle has exactly two diagonals. Those diagonals share the same midpoint and length, so they produce the same key. Conversely, any two distinct pairs of points with the same midpoint and equal length must form the diagonals of a rectangle, because the midpoint condition enforces symmetry and equal lengths ensure consistent scaling. Therefore, each rectangle corresponds to exactly one unordered pair of equal keys, and counting combinations of pairs within each group counts each rectangle exactly once.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    pts = [tuple(map(int, input().split())) for _ in range(n)]

    from collections import defaultdict
    cnt = defaultdict(int)

    for i in range(n):
        x1, y1 = pts[i]
        for j in range(i + 1, n):
            x2, y2 = pts[j]

            mx = x1 + x2
            my = y1 + y2
            dx = x1 - x2
            dy = y1 - y2
            dist2 = dx * dx + dy * dy

            cnt[(mx, my, dist2)] += 1

    ans = 0
    for k in cnt.values():
        ans += k * (k - 1) // 2

    print(ans)

if __name__ == "__main__":
    solve()

The solution builds all O(n^2) pairs and encodes each pair using integer arithmetic only. The midpoint is stored doubled, which avoids division and keeps grouping exact. The squared distance ensures rotational invariance and avoids floating-point precision issues.

The hash map accumulates how many times each potential diagonal signature appears. The final combination step converts counts into rectangle counts.

A subtle point is that using raw midpoint as a fraction would require rational normalization; doubling avoids that entirely.

Worked Examples

Example 1

Consider a simple square:

Input points:

(0,0), (0,1), (1,0), (1,1)

We enumerate all pairs.

Pair	Midpoint (x1+x2,y1+y2)	dist2	Key count
(0,0)-(1,1)	(1,1)	2	1
(0,1)-(1,0)	(1,1)	2	2
others	different	-	1 each

The key (1,1,2) appears twice, so answer = C(2,2) = 1.

This confirms that a single rectangle contributes exactly one pairing of diagonals.

Example 2

Points forming two rectangles sharing geometry:

(0,0), (0,2), (2,0), (2,2), (1,1), (1,3), (3,1), (3,3)

This creates multiple square-like structures. Each rectangle contributes two diagonal pairs, so each rectangle generates exactly one contribution in the combination formula. The grouping by midpoint ensures separation between different rectangles even if they overlap in space.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	all unordered pairs are processed once, and hash operations are O(1) average
Space	O(n^2)	in worst case every pair produces a distinct key

With n ≤ 1000, n^2 is about 1e6, which easily fits within time limits for Python and memory limits for typical CF constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import defaultdict

    n = int(input())
    pts = [tuple(map(int, input().split())) for _ in range(n)]

    cnt = defaultdict(int)

    for i in range(n):
        x1, y1 = pts[i]
        for j in range(i + 1, n):
            x2, y2 = pts[j]
            mx = x1 + x2
            my = y1 + y2
            dx = x1 - x2
            dy = y1 - y2
            dist2 = dx * dx + dy * dy
            cnt[(mx, my, dist2)] += 1

    ans = 0
    for k in cnt.values():
        ans += k * (k - 1) // 2

    return str(ans)

# sample
assert run("4\n0 0\n0 1\n1 0\n1 1\n") == "1"

# minimum non-rectangle
assert run("4\n0 0\n1 0\n2 0\n3 0\n") == "0"

# two rectangles
assert run("8\n0 0\n0 2\n2 0\n2 2\n1 1\n1 3\n3 1\n3 3\n") == "2"

# collinear + extra point
assert run("5\n0 0\n0 1\n0 2\n1 0\n2 0\n") == "0"

Test input	Expected output	What it validates
square	1	basic rectangle detection
collinear line	0	no false positives
two separated squares	2	multiple independent rectangles
degenerate mixed set	0	robustness against non-rectangles

Edge Cases

A key edge case is when many pairs share the same midpoint but not all form rectangles. The algorithm handles this correctly because midpoint alone is insufficient; the squared distance is also included in the key.

For example, consider points (0,0), (2,0), (1,1), (3,1). Pairs (0,0)-(3,1) and (2,0)-(1,1) share midpoint (3,1) and (3,1) respectively? No, midpoints differ, so they do not collide. This shows that the midpoint plus distance pairing prevents accidental grouping.

Another edge case is when multiple rectangles overlap or share vertices. The counting formula still works because it counts diagonal-pair combinations independently, and each rectangle corresponds to exactly one such pair combination within its diagonal group.