POJ.1328 Radar Installation

1. Problem
http://poj.org/problem?id=1328

2.Idea
Using greedy method, but not just based on X axis order of icelands, instead, using X axis projection segment.

X axis projection segment

3. Source:

 struct Point {  
      double x, y;  
      double s, e; //projection segment to X axis  
      bool operator < (const Point &a)const {  
           return e < a.e;  
      }  
 } Points[1003];  
 int n, d, flag;  
 int solve()  
 {  
      int ans = 1;  
      sort(Points, Points + n);  
      double r = Points[0].e;  
      for (int i = 1; i < n; i++) {  
           if (r < Points[i].s) {  
                r = Points[i].e;  
                ans++;  
           }  
      }  
      return ans;  
 }  
 int main()  
 {  
      int t = 1;  
      while (1) {  
           scanf("%d%d", &n, &d);  
           if (n + d == 0) break;  
           flag = 0;  
           for (int i = 0; i < n; i++) {  
                int x, y;  
                scanf("%d%d", &x, &y);  
                if (y > d) flag = 1;  
                Points[i].x = (double)x;  
                Points[i].y = (double)y;  
                Points[i].s = x - sqrt((double)d * d - (double)y * y);  
                Points[i].e = x + sqrt((double)d * d - (double)y * y);  
           }  
           printf("Case %d: ", t);  
           if (flag) puts("-1");  
           else printf("%d\n", solve());  
           t++;  
      }  
      return 0;  
 }