# 2022-11-24：小团在地图上放了3个定位装置，想依赖他们进行定位！ 地图是一个n*n的棋盘

2022-11-24：小团在地图上放了3个定位装置，想依赖他们进行定位！

1 <= 所有数据值 <= 50000。

``````package main

import (
"fmt"
)

func main() {
ans := find(3, []int{1, 1}, []int{3, 1}, []int{3, 4}, 3, 3, 2)
fmt.Println(ans)
}

const MAX_VALUE = 1<<31 - 1

func find(n int, a, b, c []int, ad, bd, cd int) []int {
var x1 []int
r1 := MAX_VALUE
var x2 []int
r2 := 0
var x3 []int
r3 := 0
if ad < r1 {
x1 = a
r1 = ad
x2 = b
r2 = bd
x3 = c
r3 = cd
}
if bd < r1 {
x1 = b
r1 = bd
x2 = a
r2 = ad
x3 = c
r3 = cd
}
if cd < r1 {
x1 = c
r1 = cd
x2 = a
r2 = ad
x3 = b
r3 = bd
}
// x1 r1     x2 r2 x3 r3
cur := []int{x1[0] - r1, x1[1]}
queue := make([][]int, 0)
visited := make(map[string]struct{})
ans := make([][]int, 0)
queue = append(queue, cur)
visited[fmt.Sprintf("%d_%d", cur[0], cur[1])] = struct{}{}

for len(queue) > 0 {
// cur x1为圆心，r1为半径的圆周上
cur = queue[0]
queue = queue[1:]
if cur[0] >= 1 && cur[0] <= n && cur[1] >= 1 && cur[1] <= n && distance(cur[0], cur[1], x2) == r2 && distance(cur[0], cur[1], x3) == r3 {
ans = append(ans, cur)
}
if len(ans) == 2 {
break
}
add(cur[0]-1, cur[1]-1, x1, r1, &queue, visited)
add(cur[0]-1, cur[1], x1, r1, &queue, visited)
add(cur[0]-1, cur[1]+1, x1, r1, &queue, visited)
add(cur[0], cur[1]-1, x1, r1, &queue, visited)
add(cur[0], cur[1]+1, x1, r1, &queue, visited)
add(cur[0]+1, cur[1]-1, x1, r1, &queue, visited)
add(cur[0]+1, cur[1], x1, r1, &queue, visited)
add(cur[0]+1, cur[1]+1, x1, r1, &queue, visited)
}
if len(ans) == 1 || ans[0][0] < ans[1][0] || (ans[0][0] == ans[1][0] && ans[0][1] < ans[1][1]) {
return ans[0]
} else {
return ans[1]
}
}

func add(x, y int, c []int, r int, queue *[][]int, visited map[string]struct{}) {
key := fmt.Sprintf("%d_%d", x, y)
_, ok := visited[key]
if (distance(x, y, c) == r) && !ok {
*queue = append(*queue, []int{x, y})
visited[key] = struct{}{}
}
}

func distance(x, y int, c []int) int {
return abs(x-c[0]) + abs(y-c[1])
}

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

(=￣ω￣=)··· 暂无内容！

169

10

16

5