POJ1328 Radar Installation

こういう問題苦手。わかりやすいコーナーケースに気づけなくてめちゃくちゃ時間がかかった。

解法：貪欲法。

#include <cstdio>
#include <algorithm>
#include <utility>
#include <cmath>

using namespace std;

int cas = 1;

int main(){
  
  while(1){
  
  pair<int,int> is[1003];
  
  int n,d,ans= 1;
  
  scanf("%d%d",&n,&d); if(n == 0)break;
  
  for(int i = 0;i < n;i++){
    scanf("%d%d",&is[i].first,&is[i].second);
    if(is[i].second > d) ans = -1;
  }

  sort(is, is + n);
  int k = 1,x = is[0].first,y = is[0].second;
  
  while(k < n){
    if(ans == -1)break;
    if(x + sqrt(d*d - y*y) >= is[k].first - sqrt(d*d-is[k].second*is[k].second)){
     if(x + sqrt(d*d - y*y) > is[k].first + sqrt(d*d-is[k].second*is[k].second)){
      x = is[k].first; y = is[k].second;
     }
    }else{
      ans++;
      x = is[k].first; y = is[k].second;
    }
    k++;
  }
  printf("Case %d: %d\n",cas,ans);
  cas++;
  }
  return 0;
}