1912.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1912
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 10000;
int n,l,d;
struct POINT {
	int x,y;
	bool operator < (const POINT & pt) const {
		if (x != pt.x) return x < pt.x;
		return y < pt.y;
	}
}ps[NMAX];
int get_val() {
	int ret = 0;
	char ch;
	while ((ch=getchar()) > '9' || ch < '0') ;
	do {
		ret = ret*10 + ch - '0';
	} while ((ch=getchar()) <= '9' && ch >= '0') ;
	return ret;
}
int main() {
	int i,j,ans;
	double cirx,nearx;
	while (scanf("%d %d %d",&l,&d,&n)==3) {
		for (i=0;i<n;i++) {
			ps[i].x = get_val();
			ps[i].y = get_val();
		}
		sort(ps,ps+n);
		cirx = ps[0].x + sqrt(1.0*d*d - ps[0].y*ps[0].y);
		ans = 0;
		for (i=1;i<n;i++) {
			nearx = ps[i].x - sqrt(1.0*d*d - ps[i].y*ps[i].y);
			if (cirx >= nearx) continue;
			ans ++;
			cirx = 2.0*ps[i].x - nearx;
		}
		printf("%d\n",ans+1);
	}
}