P1325 雷达安装【洛谷算法习题】

P1325 雷达安装

网页链接

P1325 雷达安装

题目描述

假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围d dd。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。

数据使用笛卡尔坐标系，定义海岸线为x xx轴。在x xx轴上方为海洋，下方为陆地。

输入格式

第一行包括2 22个整数n nn和d dd，n nn是岛屿数目，d dd是雷达扫描范围。

接下来n nn行，每行两个整数，为岛屿坐标。

输出格式

一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出-1。

输入输出样例 #1

输入 #1

3 2 1 2 -3 1 2 1

输出 #1

2

说明/提示

样例 1 解释

数据范围

对于全部数据，n ≤ 1000 n\le1000n≤1000，$ d \le 2\times 10^4， ，，| x_i | \le 2 \times 10^6， ，，0 \le y_i \le 2\times 10^4$。

解题思路

本题是经典的区间贪心选点问题，核心是将几何覆盖问题转化为区间覆盖问题求解。首先判断合法性：若岛屿纵坐标大于雷达半径，直接输出-1表示无法覆盖。对每个合法岛屿，计算其在海岸线（x轴）上可被雷达覆盖的区间[l, r]。将所有区间按右端点从小到大排序，采用贪心策略：在区间右端点放置雷达，能覆盖最多后续区间。遍历区间，若当前雷达无法覆盖该区间，则新增雷达并更新位置。最终统计最少雷达数量，算法时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)，高效适配题目数据范围。

总结

核心逻辑：几何覆盖问题转化为区间点覆盖问题，贪心选择区间右端点放置雷达。
关键操作：计算岛屿覆盖区间、按右端点排序、贪心遍历统计雷达数、预判无解场景。
效率保障：排序配合线性遍历，逻辑简洁，无冗余计算，精准解决问题。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structnd{doublel,r;}a[1010];doublecmp(nd aa,nd bb){returnaa.r<bb.r;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;doubled;cin>>n>>d;doublex[1010],y[1010];for(ll i=1;i<=n;i++){cin>>x[i]>>y[i];if(y[i]>d){cout<<"-1"<<endl;return0;}a[i].l=x[i]-sqrt(d*d-y[i]*y[i]);a[i].r=x[i]+sqrt(d*d-y[i]*y[i]);}sort(a+1,a+n+1,cmp);doubletmp;ll ans=0;for(ll i=1;i<=n;i++){if(i==1)tmp=a[i].r,ans++;elseif(tmp>a[i].l)continue;elsetmp=a[i].r,ans++;}cout<<ans<<endl;return0;}