首页 > 代码库 > HDU 1912

HDU 1912

坑,直接把公路看成X轴来做,然后,排序扫描一下,你懂的。

#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;const int MAXN=10100;struct Village{	double l,r;};Village p[MAXN];bool cmp(Village A, Village B){	if(A.l<B.l)return true;	else if(A.l==B.l){		if(A.r<B.r)return true;	}	return false;}int main(){	int n,L,D; double x,y;	while(scanf("%d%d%d",&L,&D,&n)!=EOF){		for(int i=0;i<n;i++){			scanf("%lf%lf",&x,&y);			double d=sqrt(D*D-y*y);			p[i].l=x-d; p[i].r=x+d;		}		int counted=1;		sort(p,p+n,cmp);		double s=p[0].r;		for(int i=1;i<n;i++){			if(p[i].l<=s)			continue;			else{				s=p[i].r;				counted++;			}		}		printf("%d\n",counted);	}	return 0;}