右端点排序是从左到右枚举左端点 左端点是否有大于r的
左端点排序是从右往左枚举右端点 右端点是否有小于l的
1、右端点排序
右端点排序的时候是从左到有枚举左端点 左端点是否有大于r的
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1010;
const double eps=1e-6;
int a[maxn];
int n;
pair<double, double> p[maxn];
int main(){
cin>>n;
int d;
cin>>d;
for(int i=0; i<n; i++){
int a1, b1;
cin>>a1>>b1;
if(b1>d){
cout<<"-1";
return 0;
}
double a2=a1-sqrt(d*d-b1*b1);
double a3=a1+sqrt(d*d-b1*b1);
//cout<<a2<<' '<<a3<<endl;
p[i].first=a3;//右端点排序!!!!
p[i].second=a2;
}
int ans=1;
sort(p, p+n);
double r=p[0].first;
for(int i=1; i<n; i++){
//cout<<p[i].first<<' '<<p[i].second<<endl;
if(p[i].second-r>eps){
ans++;
r=p[i].first;
}
}
cout<<ans;
return 0;
}
2、左端点排序
左端点排序是从右往左枚举右端点 右端点是否有小于l的
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1010;
const double eps=1e-6;
int a[maxn];
int n;
pair<double, double> p[maxn];
int main(){
cin>>n;
int d;
cin>>d;
for(int i=0; i<n; i++){
int a1, b1;
cin>>a1>>b1;
if(b1>d){
cout<<"-1";
return 0;
}
double a2=a1-sqrt(d*d-b1*b1);
double a3=a1+sqrt(d*d-b1*b1);
//cout<<a2<<' '<<a3<<endl;
p[i].first=a2;//左端点排序!!!!
p[i].second=a3;
}
int ans=1;
sort(p, p+n);
double l=p[n-1].first;
for(int i=n-2; i>=0; i--){
if(l-p[i].second>eps){
ans++;
l=p[i].first;
}
}
cout<<ans;
return 0;
}