Most Frequent Square

Interview

Time limit1sMemory limit128 MB

Summary
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.

figure

For example, in the figure above there are 33 squares with side length 22 and 33 squares with side length 44.

Input

The first line contains the number of test cases TT (T≤50T \le 50).

Each of the next TT lines describes one test case. A line starts with the number of points kk (k≤30k \le 30), followed by kk coordinate pairs (that is, 2k2k integers in total). Every coordinate is an integer with 0≤x,y≤300 \le x, y \le 30.

Output

For each test case, print one line.

If the points form at least one axis-parallel square, output

LENGTH = L, COUNT = C

where LL is the side length that appears in the greatest number of squares and CC is the number of squares with that side length. If several side lengths tie for the greatest count, use the largest such side length LL.

If the points form no axis-parallel square at all, output

No squares among the points.

Examples1

  1. Example 1

    Input
    8
    4 0 0 1 1 0 1 1 0 
    4 0 0 2 1 0 1 1 0 
    4 0 0 2 2 0 2 2 0 
    9 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
    9 0 0 0 2 0 4 2 0 2 2 2 4 4 0 4 2 4 4
    10 2 3 0 2 2 1 2 0 1 1 1 2 3 3 3 0 0 1 0 0 
    10 2 0 3 2 0 1 2 1 1 0 3 3 1 3 2 3 2 2 3 0 
    10 3 1 2 2 3 3 0 2 0 0 2 0 0 1 1 1 1 3 1 2 
    
    Expected output
    LENGTH = 1, COUNT = 1
    No squares among the points.
    LENGTH = 2, COUNT = 1
    LENGTH = 1, COUNT = 4
    LENGTH = 2, COUNT = 4
    LENGTH = 1, COUNT = 1
    LENGTH = 1, COUNT = 1
    LENGTH = 2, COUNT = 2