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代码
