记录编号	559086	评测结果	AAAAAAAAAA
题目名称	[POJ 1328]监控安装	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2021-02-13 03:03:17	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1005;
double x[maxn],y[maxn];
int n,rk[maxn];
double R;
double l[maxn],r[maxn];
bool cmp(int a,int b) {
	return l[a] == l[b] ? r[a] < r[b] : l[a] < l[b];
}
int main() {
	freopen("monitor.in","r",stdin);
	freopen("monitor.out","w",stdout);
	scanf("%d%lf",&n,&R);
	for(int i = 1;i <= n;++ i) {
		rk[i] = i;
		scanf("%lf%lf",&x[i],&y[i]);
		if(y[i] > R) {
			puts("-1");
			return 0;
		}
		double b = x[i],d = R * R - y[i] * y[i];
		l[i] = b - sqrt(d);
		r[i] = b + sqrt(d);
		if(l[i] > r[i])swap(l[i] , r[i]); 
	}        
	double pos = -1e6;
	int ans = 0;
	sort(rk + 1 , rk + 1 + n , cmp);
//	for(int i = 1;i <= n;++ i) {
//		printf("%.2lf %.2lf\n",l[rk[i]],r[rk[i]]);
//	}
	for(int i = 1;i <= n;++ i) {
		int p = rk[i];
		if(pos < l[p]) {
			++ ans;
			pos = r[p];//++
		}
		else {
			pos = min(r[p]/*++*/ , pos);
		}
	}
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}