CareerCup

package main

import "fmt"

type Point struct {
	x, y int
}

func Abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func FindSquares(p []Point) [][]Point {
	m := map[int]map[int]int{}
	for i, point := range p {
		if _, ok := m[point.x]; !ok {
			m[point.x] = map[int]int{}
		}
		m[point.x][point.y] = i
	}
	res := [][]Point{}
	for i := 0; i < len(p)-1; i++ {
		for j := i + 1; j < len(p); j++ {
			if Abs(p[i].x-p[j].x) == Abs(p[i].y-p[j].y) {
				_, ok1 := m[p[i].x][p[j].y]
				_, ok2 := m[p[j].x][p[i].y]
				if ok1 && ok2 {
					found := []Point{
						p[i],
						p[j],
						p[m[p[i].x][p[j].y]],
						p[m[p[j].x][p[i].y]],
					}
					res = append(res, found)
				}
			}
		}
		delete(m[p[i].x], p[i].y)
	}
	return res
}

func main() {
	input := []Point{
		Point{1, 1},
		Point{3, 1},
		Point{4, 2},
		Point{3, 3},
		Point{1, 4},
		Point{1, 3},
		Point{4, 1},
		Point{3, 2},
	}
	fmt.Println(FindSquares(input))
}

bool isSquare(Point p1, Point p2, Point p3, Point p4) 
{ 
    int d2 = distSq(p1, p2); // from p1 to p2 
    int d3 = distSq(p1, p3); // from p1 to p3 
    int d4 = distSq(p1, p4); // from p1 to p4 
  
    // If lengths if (p1, p2) and (p1, p3) are same, then 
    // following conditions must met to form a square. 
    // 1) Square of length of (p1, p4) is same as twice 
    // the square of (p1, p2) 
    // 2) Square of length of (p2, p3) is same as twice the square of (p1, p2) 
  
    if (d2 == d3 && 2 * d2 == d4 && 2 * d2 == distSq(p2, p3)) { 
        int d = distSq(p2, p4); 
        return (d == distSq(p3, p4) && d == d2); 
    } 
  
    // The below two cases are similar to above case 
    if (d3 == d4 && 2 * d3 == d2 && 2 * d3 == distSq(p3, p4)) { 
        int d = distSq(p2, p3); 
        return (d == distSq(p2, p4) && d == d3); 
    } 
    if (d2 == d4 && 2 * d2 == d3 && 2 * d2 == distSq(p2, p4)) { 
        int d = distSq(p2, p3); 
        return (d == distSq(p3, p4) && d == d2); 
    } 
  
    return false; 
}

for every set of 4 points (a, b, c, d)

'ab' and 'cd' are either opposite sides or diagonals, in a square they have to be equal
if they are sides, then either 'ac' is a side and 'ad' a diagonal or vice versa
if they are diagonals, then 'ac', 'bc', 'ad' and 'bd' are the 4 sides

Note that a,b,c,d are labelled without loss of generality i.e. for every set of 4 points (x1,y1), (x2,y2), (x3,y3), (x4,y4), label them as a,b,c,d in any order