UVa 1193 Radar Installation

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <algorithm>

 4  #include <iostream>

 5  #include <math.h>

 6  using namespace std;

 7  int main()

 8  {

 9      int n,d,cas=1;

10      while(cin>>n>>d && n+d)

11      {

12          pair<double,double> p[1005];

13          for(int i=0; i<n; i++)

14          {

15 

16              double h;

17              double x,y;

18              cin>>x>>y;

19              if(d==-1) continue;

20              if(y>d)

21              {

22                  d=-1;

23                  continue;

24              }

25              h=sqrt(d*d-y*y)+ 1e-8;

26              p[i].first=x-h;

27              p[i].second=x+h;

28          }

29 

30          if(d==-1) printf("Case %d: -1\n",cas++);

31          else

32          {

33              sort(p,p+n);

34              double last=-(1e+60);

35              int ans=0;

36              for(int i=0; i<n; i++)

37              {

38                  if(p[i].first<=last)

39                  {

40                      last=min(last,p[i].second);

41                      continue;

42                  }

43                  ans++;

44                  last=p[i].second;

45 

46              }

47              printf("Case %d: %d\n",cas++,ans);

48          }

49      }

50      return 0;

51  }