题目描述有些坑。。
题意：
有一条高速公路在x轴上，从（0,0）到（L,0）。周围有一些村庄，希望能够在高速公路上开通几个出口，使得每个村庄到最近的出口距离小于D，求出最少需要开通多少个出口。
解题思路：
典型的区间问题，将每个点化为区间（x-sqrt(D^2-y^2),x+sqrt(D^2+y^2)），然后按区间右端点排序，依次对每个区间进行操作，如果该区间中已有出口则无需增加，若该区间没有出口则取右端点为出口。
可以证明，这是最优方案，得到最少出口数。
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #define eps 1e-6 using namespace std; int n,ans; double p,q,h,L,D; struct point{ double x,y; }a[1000000]; bool cmp(point a,point b){ if(a.y<b.y) return 1; return 0; } int main() { while(scanf("%lf%lf%d",&L,&D,&n)==3){ for(int i=0;i<n;i++){ scanf("%lf%lf",&p,&q); a[i].x=p-sqrt(fabs(D*D-q*q)); a[i].y=p+sqrt(fabs(D*D-q*q)); } sort(a,a+n,cmp); h=-100000; ans=0; for(int i=0;i<n;i++) if(!((h>a[i].x||fabs(h-a[i].x)<eps)&&(h<a[i].y||fabs(h-a[i].y<eps)))){ h=a[i].y; if(h>L&&fabs(h-L)>eps) h=L; ans++; } printf("%d",ans); } return 0; }
原文：http://www.cnblogs.com/Mathics/p/3849356.html