input
n d 1<=n<=1000
n行坐标xi,yi
output
位于x轴扫描器的扫描距离为d，至少要多少个扫描器才能扫描到所有坐标
如果无法扫描完输出-1，否则输出扫描器个数
做法：将每个坐标转化为扫描器可扫到它的区间，然后取最少区间，最少区间为最多的不连续区间数
1 #include<cstdio> 2 #include<cmath> 3 #include<cstdlib> 4 #define INF 1e-8 5 6 int n, cas=1; 7 double x[1010][2], d; 8 int cmp(const void*a,const void*b) 9 { 10 double*c=(double*)a,*d=(double*)b; 11 if(c[0]!=d[0]) return c[0]>d[0]?1:0; 12 return c[1]>d[1]?1:0; 13 } 14 int main() 15 { 16 freopen("/home/user/桌面/in","r",stdin); 17 while (scanf("%d%lf", &n, &d) == 2&& n) 18 { 19 int i,work=1,x0,y0; 20 for (i = 0; i < n; i++) 21 { 22 scanf("%d%d", &x0, &y0); 23 if (y0 > d||y0<0) 24 { 25 work = 0; 26 for(i++;i<n;i++) 27 scanf("%*d%*d"); 28 break; 29 } 30 double t = sqrt(d*d - y0 * y0); 31 x[i][0] = x0 - t; 32 x[i][1] = x0 + t; 33 } 34 printf("Case %d: ", cas++); 35 if (!work) 36 { 37 puts("-1"); 38 continue; 39 } 40 qsort(x,n,sizeof(x[0]),cmp); 41 // for(int i=0;i<n;i++) printf("%lf %lf ",x[i][0],x[i][1]); 42 int j=1; 43 d=x[0][1]; 44 for(i=1;i<n;i++) 45 { 46 if(x[i][0]<=d) {if(x[i][1]<d) d=x[i][1];} 47 else 48 { 49 j++; 50 d=x[i][1]; 51 } 52 } 53 printf("%d ", j); 54 } 55 return 0; 56 }