雷達裝置

ybtoj 貪心-1-2

題目大意

在平面直角坐標系中有n個點，現在讓你在x軸上布置雷達，雷達可以的偵查半徑為d，問你最少布置多少個雷達

輸入樣例

3 2 1 2 -3 1 2 1

輸出樣例

2

數據范圍

$1?n?10^3$

解題思路

首先通過勾股定理求出偵查該點的雷達x坐標范圍
然后按范圍的右端坐標排序
第一個雷達放在第一個點的右端坐標
然后每次判斷上一個點是否在范圍內
如果不在就再建一個

代碼

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define abs(y) (y>0?y:-y) using namespace std; int n, ans; double d, x, y, g; struct node {double l, r; }a[1010]; bool cmp(node a, node b) {return a.r < b.r; } int main() {scanf("%d%lf", &n, &d);for (int i = 1; i <= n; ++i){scanf("%lf%lf", &x, &y);if (abs(y) > d)//無法達到{printf("-1");return 0;}a[i].l = x - sqrt((d * d - y * y));//左右端a[i].r = x + sqrt((d * d - y * y));}sort(a+1,a+1+n,cmp);ans = 1;g = a[1].r;//范圍的右端for (int i = 2; i <= n; ++i)if (a[i].l > g) g = a[i].r, ans++;printf("%d", ans);return 0; }

總結

以上是生活随笔為你收集整理的【贪心】雷达装置（ybtoj 贪心-1-2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。