/* -*- coding: utf-8 -*- * * 1121.cc: No.1121 Social Distancing in Cinema - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 250000; const int D = 10; const int DD = D * D; /* typedef */ struct Pt { int y, x, i; Pt() {} Pt(int _y, int _x, int _i): y(_y), x(_x), i(_i) {} bool operator<(const Pt &p) const { return y < p.y || (y == p.y && x < p.x); } int d2(const Pt &p) const { int dx = x - p.x, dy = y - p.y; return dx * dx + dy * dy; } void print() { printf("(%d,%d,%d)\n", y, x, i); } }; typedef set spt; /* global variables */ Pt ps[MAX_N]; spt pset; bool used[MAX_N]; int vs[MAX_N]; /* subroutines */ bool cmpptx(const Pt &p, const Pt &q) { return p.x < q.x || (p.x == q.x && p.y < q.y); } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &ps[i].x, &ps[i].y), ps[i].i = i; sort(ps, ps + n, cmpptx); int k = 0; for (int i = 0, j = 0; i < n; i++) { Pt pi = ps[i]; //printf("i=%d: ", i), pi.print(); while (j < i && ps[j].x < pi.x - D) { if (used[j]) pset.erase(ps[j]); j++; } //printf(" %lu\n", pset.size()); bool ok = true; spt::iterator sit = lower_bound(pset.begin(), pset.end(), Pt(pi.y - D, -1, -1)); for(; sit != pset.end() && sit->y - pi.y <= D; sit++) { if (sit->d2(pi) <= DD) { ok = false; break; } } if (ok) { used[i] = true; vs[k++] = ps[i].i; pset.insert(pi); } } printf("%d\n", k); for (int i = 0; i < k; i++) { printf("%d", vs[i] + 1); putchar(i + 1 < k ? ' ' : '\n'); } return 0; }