呢么問題就變成了區(qū)間合并問題。給我們n給區(qū)間將相交的區(qū)間合并求不相交的區(qū)間個數(shù)。

#include<bits/stdc++.h> using namespace std; typedef pair<double,double> pdd; int n,r,flag; vector<pdd>ve; int main(void) {cin>>n>>r;for(int i=0;i<n;i++){double x,y; cin>>x>>y;if(y>r) flag=1;double len=sqrt(r*r-y*y);ve.push_back({x+len,x-len});}double last=-1e9;int cnt=0;sort(ve.begin(),ve.end());for(int i=0;i<ve.size();i++)if(ve[i].second>last) last=ve[i].first,cnt++;if(flag) puts("-1");else cout<<cnt;return 0; }

總結(jié)

以上是生活随笔為你收集整理的112. 雷达设备【贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。