帮忙看看为什么第三点过不了
查看原帖
帮忙看看为什么第三点过不了
134805
jmz20060119楼主2020/11/21 14:50
#include <bits/stdc++.h>  //贪心 
using namespace std;
double a[1001][3],b[1001][3];
int main()	
{
	int n,o,ans=0;
	double d;
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i][1]>>a[i][2];
		if(a[i][2]>d){
			cout<<-1;
			return 0; 
		} 
		b[i][1]=a[i][1]-sqrt(d*d-a[i][2]*a[i][2]);
		b[i][2]=a[i][1]+sqrt(d*d-a[i][2]*a[i][2]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(b[j][2]<b[i][2]){
				swap(b[j][1],b[i][1]);
				swap(b[j][2],b[i][2]);
			}
			if (b[j][2]==b[i][2]){
				if(b[j][1]<b[i][1]){
					swap(b[j][1],b[i][1]);
				    swap(b[j][2],b[i][2]);
				}
			}
		}
	} //右端点排序  
	ans=1;
	o=b[1][2];
	for(int i=2;i<=n;i++){
		if(o>=b[i][1]&&o<=b[i][2]) continue;
		o=b[i][2];
		ans++;
	}//放最右边一定是最优的 
	cout<<ans;
}
2020/11/21 14:50
加载中...