整个二维平面算是一张地图,给定[x,y],表示你站在x行y列,
你可以选择面朝的任何方向,
给定一个正数值angle,表示你视野的角度为,
这个角度内你可以看无穷远,这个角度外你看不到任何东西。
给定一批点的二维坐标,
返回你在朝向最好的情况下,最多能看到几个点。
第一步:把x,y平移到原点上。
第二步:把所有点放在单位圆上,算出夹角。
第三步:不回退计算。在原点的点需要单独算。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math"
"sort"
)
func main() {
points := [][]int{{2, 1}, {2, 2}, {3, 3}}
angle := 90
location := []int{1, 1}
ret := visiblePoints(points, angle, location)
fmt.Println(ret)
}
func visiblePoints(points [][]int, angle int, location []int) int {
n := len(points)
a := location[0]
b := location[1]
zero := 0
arr := make([]float64, n<<1)
m := 0
for i := 0; i < n; i++ {
x := points[i][0] - a
y := points[i][1] - b
if x == 0 && y == 0 {
zero++
} else {
math.Atan2(float64(y), float64(x))
arr[m] = toDegrees(math.Atan2(float64(y), float64(x)))
arr[m+1] = arr[m] + 360
m += 2
}
}
sort.Float64s(arr[0:m])
max := 0
for L, R := 0, 0; L < n; L++ {
for R < m && arr[R]-arr[L] <= float64(angle) {
R++
}
max = getMax(max, R-L)
}
return max + zero
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func toDegrees(x float64) float64 {
return x * (180.0 / math.Pi)
}
执行结果如下: