leetcode-go/bailian/1328.radar-installation/main.cc

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <limits>

using namespace std;

const double eps = 1e-6;

int n, d, id = 0;

struct Island {
  double rs;
  double re;
  void set(int x, int y) {
    double dx = sqrt(double(d) * d - double(y) * y);
    rs = x - dx;
    re = x + dx;
  }
  bool operator<(const Island &that) { return this->rs < that.rs; }
};

int main() {
  Island is[1000];
  while (scanf("%d %d", &n, &d) != EOF && (n != 0 || d != 0)) {
    int x, y, cnt = 0;
    for (int i = 0; i < n; i++) {
      scanf("%d %d", &x, &y);
      if (d < fabs(y)) {  // !!!y maybe negative
        cnt = -1;
        continue;
      }
      is[i].set(x, y);
    }
    if (cnt == 0) {
      sort(is, is + n);
      // Avoid overflow, use -max instead of min
      double end = -numeric_limits<double>::max();
      for (int i = 0; i < n; i++) {
        if (is[i].rs - end > eps) {
          cnt++;
          end = is[i].re;
        } else if (end - is[i].re > eps) {
          end = is[i].re;
        }
      }
    }
    printf("Case %d: %d\n", ++id, cnt);
  }
  return 0;
}