摘要
Title: 112. 雷达设备
Tag: 区间并集
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

112. 雷达设备

• 题意

  假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
  每个小岛都位于海洋一侧的某个点上。
  雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。
  我们使用笛卡尔坐标系，定义海岸线为 x 轴，海的一侧在 x 轴上方，陆地一侧在 x 轴下方。
  现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目

• 思路

  题目大意：雷达只能放在x轴上，雷达的半径为d，问最少选几个雷达，能全覆盖所有岛

  ---

  逆向思维想，反过来想，每个岛可接受的雷达的区间是多少，算出所有的区间，那么区间之间的交集数量，就是我们要求的
  题目转化为了：Acwing 905. 区间选点

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-30 15:56:43
  FilePath: \ACM\Acwing\112.py
  LastEditTime: 2022-03-30 15:56:43
  '''
  n, d = map(int, input().split())
  pos = []
  for i in range(n):
      pos.append(tuple(map(int, input().split())))
  
  a = []
  for x, y in pos:
      if y > d:
          print(-1)
          exit(0)
      D = pow(d * d - y * y, 0.5)
      a.append([x - D, x + D])
  
  a.sort(key=lambda x: x[1])
  R = -int(2e9)
  ans = 0
  for l, r in a:
      if l > R:
          ans += 1
          R = r
  
  print(ans)