P1325 雷达安装网页链接P1325 雷达安装题目描述假设海岸线是一条无限延伸的直线。它的一侧是陆地另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上包括海岸线并且每个雷达都有相同的扫描范围d dd。你的任务是建立尽量少的雷达站使所有小岛都在扫描范围之内。数据使用笛卡尔坐标系定义海岸线为x xx轴。在x xx轴上方为海洋下方为陆地。输入格式第一行包括2 22个整数n nn和d ddn nn是岛屿数目d dd是雷达扫描范围。接下来n nn行每行两个整数为岛屿坐标。输出格式一个整数表示最少需要的雷达数目若不可能覆盖所有岛屿输出-1。输入输出样例 #1输入 #13 2 1 2 -3 1 2 1输出 #12说明/提示样例 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)高效适配题目数据范围。总结核心逻辑几何覆盖问题转化为区间点覆盖问题贪心选择区间右端点放置雷达。关键操作计算岛屿覆盖区间、按右端点排序、贪心遍历统计雷达数、预判无解场景。效率保障排序配合线性遍历逻辑简洁无冗余计算精准解决问题。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structnd{doublel,r;}a[1010];doublecmp(nd aa,nd bb){returnaa.rbb.r;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;doubled;cinnd;doublex[1010],y[1010];for(ll i1;in;i){cinx[i]y[i];if(y[i]d){cout-1endl;return0;}a[i].lx[i]-sqrt(d*d-y[i]*y[i]);a[i].rx[i]sqrt(d*d-y[i]*y[i]);}sort(a1,an1,cmp);doubletmp;ll ans0;for(ll i1;in;i){if(i1)tmpa[i].r,ans;elseif(tmpa[i].l)continue;elsetmpa[i].r,ans;}coutansendl;return0;}