ACM入门题-安装雷达-Go语言

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB
分数：100

描述

有一海岸线（x轴），一半是陆地（y<0）、一半是海（y>0），海上有一些小岛（用坐标点表示P1、P2…），现要在海岸线上建雷达（覆盖半径R）。给出所有小岛的位置，和雷达半径，求最少需要多少个雷达？

输入描述

输入由几个测试用例组成。 每个用例的第一行包含两个整数 n (1<=n<=1000) 和 d，其中 n 是海中岛屿的数量，d 是雷达装置的覆盖距离。 接下来是 n 行，每行包含两个整数，表示每个岛的位置坐标(x,y)。 然后是一个空行来分隔这些案例。
为方便起见，假设：
1<=d<=2³⁰.
-2³⁰<=x<=2³⁰
0<y<=2³⁰

输出描述

对于每个测试用例输出一行，由测试用例编号和所需的最少雷达安装数组成。 “-1”安装意味着这种情况没有解决方案。

思路：

1. 知道小岛位置，和雷达半径，那么以小岛为圆心，雷达覆盖半径为半径画圆，可以求出小岛与x轴有0（雷达无法覆盖）、1（雷达只能在这个点上才能覆盖）、2个交点（雷达在两点之间都能覆盖该小岛）

2. 要求最少雷达多少个，即把雷达放在1中线段的交集内。

那么这就变成了线段交集问题。（贪心）

AC代码：

package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	var n, d, res int
	impossible := false
	type line struct {
		left  float64
		right float64
	}
	var dx float64
	fmt.Scan(&n, &d)
	an := make([][]int, n)
	lines := make([]line, n)
	for i := 0; i < n; i++ {
		an[i] = make([]int, 2)
		fmt.Scan(&an[i][0], &an[i][1])
		if an[i][1] > d {
			impossible = true
		}
		dx = math.Sqrt(float64(d*d) - float64(an[i][1]*an[i][1]))
		lines[i] = line{float64(an[i][0]) - dx, float64(an[i][0]) + dx}
	}
	if impossible {
		fmt.Println(-1)
		return
	}
	sort.Slice(lines, func(i, j int) bool { return lines[i].left < lines[j].left })	// 排序
	res++
	tmp := lines[0].right
	for i := 1; i < n; i++ {	// 贪心查找
		if lines[i].left > tmp {
			res++
			tmp = lines[i].right
		} else if lines[i].right < tmp {
			tmp = lines[i].right
		}
	}
	fmt.Println(res)
}

最后

以上就是搞怪纸鹤为你收集整理的ACM入门题-安装雷达-Go语言ACM入门题-安装雷达-Go语言的全部内容，希望文章能够帮你解决ACM入门题-安装雷达-Go语言ACM入门题-安装雷达-Go语言所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。