Most Frequent Square
InterviewTime limit1sMemory limit128 MB
Given up to 30 integer grid points, count all axis-parallel squares formed by four of them and report the side length with the most squares, breaking ties by the largest length.
- Level
Medium4 of 10
- Topics
- Brute force, Geometry, Hash map, Implementation
- Solved
- No attempts yet
Problem
You are given a set of grid points in the plane. Consider every axis-parallel square whose four corners all belong to the given set — a square whose sides are horizontal and vertical and are never tilted. Determine which side length occurs in the greatest number of such squares, and how many squares have that side length.

For example, in the figure above there are squares with side length and squares with side length .
Input
The first line contains the number of test cases ().
Each of the next lines describes one test case. A line starts with the number of points (), followed by coordinate pairs (that is, integers in total). Every coordinate is an integer with .
Output
For each test case, print one line.
If the points form at least one axis-parallel square, output
LENGTH = L, COUNT = C
where is the side length that appears in the greatest number of squares and is the number of squares with that side length. If several side lengths tie for the greatest count, use the largest such side length .
If the points form no axis-parallel square at all, output
No squares among the points.