Detect Squares

Description

Store points with multiplicity. count(query) returns how many positive-area axis-aligned squares can be formed using query and three stored point occurrences. The query itself need not have been stored.

Solution

from collections import Counter

def create_detect_squares():
    return Counter()

def add(state, point):
    state[tuple(point)] += 1

def count(state, point):
    x, y = point
    total = 0
    for (px, py), frequency in state.items():
        if px == x and py != y:
            side = py - y
            for nx in (x + side, x - side):
                total += frequency * state[(nx, y)] * state[(nx, py)]
    return total

Examples

Approach

Count stored coordinate pairs. For each stored point vertically aligned with the query, use their vertical difference as the square side length. Check the two possible horizontal directions and multiply the three corner frequencies.