leetcode-go/leetcode/hard/149.go

package main

// Tuple3Int ...
type Tuple3Int struct {
	_1 int
	_2 int
	_3 int
}

/**
 * Definition for a point.
 * type Point struct {
 *     X int
 *     Y int
 * }
 */
func maxPoints(points []Point) (maxPts int) {
	xAxisDir := make(map[int]int)
	yAxisDir := make(map[int]int)
	weight := make(map[Point]int)
	for i := range points {
		xAxisDir[points[i].X]++
		yAxisDir[points[i].Y]++
		weight[points[i]]++
	}
	lines := make(map[Tuple3Int]map[Point]int)
	for i := 0; i < len(points); i++ {
		for j := i + 1; j < len(points); j++ {
			if points[i].X != points[j].X && points[i].Y != points[j].Y {
				pair := getParamsOfLine(points[i], points[j])
				if _, ok := lines[pair]; !ok {
					lines[pair] = make(map[Point]int)
				}
				if _, ok := lines[pair][points[i]]; !ok {
					lines[pair][points[i]] += weight[points[i]]
				}
				if _, ok := lines[pair][points[j]]; !ok {
					lines[pair][points[j]] += weight[points[j]]
				}
			}
		}
	}
	for _, v := range xAxisDir {
		if v > maxPts {
			maxPts = v
		}
	}
	for _, v := range yAxisDir {
		if v > maxPts {
			maxPts = v
		}
	}
	for _, m := range lines {
		pts := 0
		for _, v := range m {
			pts += v
		}
		if pts > maxPts {
			maxPts = pts
		}
	}
	return
}

// Caculate params of given line ay = bx + c, return Tuple3Int{a, b, c}
func getParamsOfLine(p1, p2 Point) Tuple3Int {
	y, x := p2.Y-p1.Y, p2.X-p1.X
	a, b := x, y
	for b != 0 {
		a, b = b, a%b
	}
	return Tuple3Int{x / a, y / a, (x*p1.Y - y*p1.X) / a}
}

// func main() {
// 	println(maxPoints(
// 		[]Point{{1, 1}, {2, 2}, {1, 1}}))
// 	println(maxPoints(
// 		[]Point{{1, 1}, {2, 2}, {3, 3}}))
// 	println(maxPoints(
// 		[]Point{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}))
// }