村 (KUPC 2012)

http://kupc2012.contest.atcoder.jp/tasks/kupc2012_7#

問題

略

解法

解説参照。ソースは平面走査の解答。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
double r;
struct Event {
  int index;
  double y;
  double x;
  int inout;
  Event() {;}
  Event(int index, double x, double y, int inout)
    : index(index), y(y), x(x), inout(inout) {;}
  bool operator<(const Event &rhs) const {
    return y + inout * r * 1.2 < rhs.y + rhs.inout * r * 1.2;
  }
};

set<pair<double, double> > ps;
double ys[200010];
double xs[200010];
Event events[400010];

int main() {
  while (scanf("%d %lf", &n, &r) > 0) {
    int ans = 0;
    ps.clear();
    ps.insert(make_pair(1e+100, 1e+100));
    ps.insert(make_pair(1e+101, 1e+101));
    ps.insert(make_pair(1e+102, 1e+102));
    ps.insert(make_pair(1e+103, 1e+103));
    REP(i, n) {
      int v = scanf("%lf %lf", &xs[i], &ys[i]);
      assert(v == 2);
      events[i * 2 + 0] = Event(i, xs[i], ys[i], 0);
      events[i * 2 + 1] = Event(i, xs[i], ys[i], 1);
    }
    sort(events, events + 2 * n);
    REP(i, 2 * n) {
      Event &e = events[i];
      if (e.inout == 1) {
        if (ps.count(make_pair(e.x, e.y))) { ps.erase(make_pair(e.x, e.y)); }
      } else {
        set<pair<double, double> >::iterator it = ps.lower_bound(make_pair(e.x - r * 1.2, -1e+10));
        if (hypot(e.x - it->first, e.y - it->second) <= r * 1.5) { continue; }
        it++;
        if (hypot(e.x - it->first, e.y - it->second) <= r * 1.5) { continue; }
        ps.insert(make_pair(e.x, e.y));
        ans++;
      }
    }
    printf("%d\n", ans);
  }
}