2022-03-17：所有黑洞的中心点记录在holes数组里， 比如[[3,5] [6,9]]表示，第一个黑洞

2022-03-17：所有黑洞的中心点记录在holes数组里， 比如[[3,5] [6,9]]表示，第一个黑洞在(3,5)，第二个黑洞在(6,9)， 并且所有黑洞的中心点都在左下角(0,0)，右上角(x,y)的区域里， 飞船一旦开始进入黑洞，就会被吸进黑洞里。 返回如果统一所有黑洞的半径，最大半径是多少， 依然能保证飞船从(0,0)能到达(x,y)。 来自美团。

答案2022-03-17：

二分答案+并查集。

代码用golang编写。代码如下：

package main

import (
	"fmt"
	"math"
)

func main() {
	holes := [][]int{{3, 5}, {6, 9}}
	x := 11
	y := 11
	fmt.Println(maxRadius(holes, x, y))
}

func maxRadius(holes [][]int, x, y int) int {
	L := 1
	R := getMax(x, y)
	ans := 0
	for L <= R {
		M := (L + R) / 2
		if ok(holes, M, x, y) {
			ans = M
			L = M + 1
		} else {
			R = M - 1
		}
	}
	return ans
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func ok(holes [][]int, r, x, y int) bool {
	n := len(holes)
	uf := NewUnionFind(holes, n, r)
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			if touch(holes[i][0], holes[i][1], holes[j][0], holes[j][1], r) {
				uf.union(i, j)
			}
			if uf.block(i, x, y) {
				return false
			}
		}
	}
	return true
}

func touch(x1, y1, x2, y2, r int) bool {
	return (r<<1)*(r<<1) < abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2)
	//return (r << 1) >= sqrt(abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2))
}

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

func sqrt(a int) int {
	return int(math.Sqrt(float64(a)))
}

type UnionFind struct {
	father []int
	size   []int
	xmin   []int
	xmax   []int
	ymin   []int
	ymax   []int
	help   []int
}

func NewUnionFind(holes [][]int, n, r int) *UnionFind {
	ans := &UnionFind{}
	ans.father = make([]int, n)
	ans.size = make([]int, n)
	ans.xmin = make([]int, n)
	ans.xmax = make([]int, n)
	ans.ymin = make([]int, n)
	ans.ymax = make([]int, n)
	ans.help = make([]int, n)
	for i := 0; i < n; i++ {
		ans.father[i] = i
		ans.size[i] = 1
		ans.xmin[i] = holes[i][0] - r
		ans.xmax[i] = holes[i][0] + r
		ans.ymin[i] = holes[i][1] - r
		ans.ymax[i] = holes[i][1] + r
	}
	return ans
}

func (this *UnionFind) find(i int) int {
	hi := 0
	for i != this.father[i] {
		this.help[hi] = i
		hi++
		i = this.father[i]
	}
	for hi--; hi >= 0; hi-- {
		this.father[this.help[hi]] = i
	}
	return i
}

func (this *UnionFind) union(i, j int) {
	fatheri := this.find(i)
	fatherj := this.find(j)
	if fatheri != fatherj {
		sizei := this.size[fatheri]
		sizej := this.size[fatherj]
		big := twoSelectOne(sizei >= sizej, fatheri, fatherj)
		small := twoSelectOne(big == fatheri, fatherj, fatheri)
		this.father[small] = big
		this.size[big] = sizei + sizej
		this.xmin[big] = getMin(this.xmin[big], this.xmin[small])
		this.xmax[big] = getMax(this.xmax[big], this.xmax[small])
		this.ymin[big] = getMin(this.ymin[big], this.ymin[small])
		this.ymax[big] = getMax(this.ymax[big], this.ymax[small])
	}
}

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func twoSelectOne(c bool, a, b int) int {
	if c {
		return a
	} else {
		return b
	}
}

func (this *UnionFind) block(i, x, y int) bool {
	i = this.find(i)
	return (this.xmin[i] <= 0 && this.xmax[i] >= x) ||
		(this.ymin[i] <= 0 && this.ymax[i] >= y) ||
		(this.xmin[i] <= 0 && this.ymin[i] <= 0) ||
		(this.xmax[i] >= x && this.ymax[i] >= y)
}

执行结果如下：

左神java代码