#include using namespace std; #define DEBUG(x) cerr<<#x<<": "< #define vl vector #define vii vector< vector > #define vll vector< vector > #define vs vector #define pii pair #define pis pair #define psi pair #define pll pair template pair operator+(const pair &s, const pair &t) { return pair(s.first + t.first, s.second + t.second); } template pair operator-(const pair &s, const pair &t) { return pair(s.first - t.first, s.second - t.second); } template ostream& operator<<(ostream& os, pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define X first #define Y second #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--) #define rrep1(i,n) for(int i=(int)(n);i>0;i--) #define REP(i,a,b) for(int i=a;i bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; } #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); const ll inf = 1000000001; const ll INF = (ll)1e18 + 1; const long double pi = 3.1415926535897932384626433832795028841971L; #define Sp(p) cout<> x2y, map xy2i, vector xy) { vi num(n); priority_queue, greater> pq; rep (x, 501) { for (auto itr = x2y[x].begin(); itr != x2y[x].end(); itr++) { int y = *itr; for (int add = -9; add <= 9; add++) { int nx = x + add; if (not in(nx, 0, 501)) continue; auto itr = x2y[nx].lower_bound(y - 9); while (true) { if (itr == x2y[nx].end()) break; int ny = *itr; if (dist(x, y, nx, ny) < 100) { num[xy2i[pii(x, y)]]++; itr++; } else { if (ny <= y) itr++; else break; } } } } } // DEBUG_VEC(num); vector used(n); rep (i, n) pq.push(pii(num[i], i)); int k = 0; vi ans; while (k * 90 < n) { if (pq.size() == 0) return false; pii temp = pq.top(); pq.pop(); if (used[temp.second]) continue; int x = xy[temp.second].first, y = xy[temp.second].second; if (x2y[x].count(y) == 0) continue; used[temp.second] = true; k++; ans.push_back(temp.second); vector era_xy; for (int add = -9; add <= 9; add++) { int nx = x + add; if (not in(nx, 0, 501)) continue; auto itr = x2y[nx].lower_bound(y - 9); while (true) { if (itr == x2y[nx].end()) break; int ny = *itr; if (dist(x, y, nx, ny) < 100) { x2y[nx].erase(itr); itr = x2y[nx].lower_bound(ny); era_xy.push_back(pii(nx, ny)); } else { if (ny <= y) itr++; else break; } } } set xxyy; rep (i, era_xy.size()) { int x = era_xy[i].first, y = era_xy[i].second; for (int add = -9; add <= 9; add++) { int nx = x + add; if (not in(nx, 0, 501)) continue; auto itr = x2y[nx].lower_bound(y - 9); while (true) { if (itr == x2y[nx].end()) break; int ny = *itr; if (dist(x, y, nx, ny) < 100) { num[xy2i[pii(nx, ny)]]--; xxyy.insert(pii(nx, ny)); itr++; } else { if (ny <= y) itr++; else break; } } } } for (auto itr = xxyy.begin(); itr != xxyy.end(); itr++) { int x = itr->first, y = itr->second; int idx = xy2i[pii(x, y)]; pq.push(pii(num[idx], idx)); } } // rep (i, ans.size()) { // for (int j = i + 1; j < ans.size(); j++) { // if (dist(xy[ans[i]].first, xy[ans[i]].second, xy[ans[j]].first, xy[ans[j]].second) < 100) assert(false); // } // } cout << k << endl; rep (i, ans.size()) cout << ans[i] + 1 << " "; cout << endl; return true; } bool solve2(int n, vector> x2y, map xy2i, vector xy, bool x_flip, bool y_flip, bool rotate) { rep (x, 501) { for (auto itr = x2y[x].begin(); itr != x2y[x].end(); itr++) { int y = *itr; for (int add = -9; add <= 9; add++) { int nx = x + add; if (not in(nx, 0, 501)) continue; auto itr = x2y[nx].lower_bound(y - 9); while (true) { if (itr == x2y[nx].end()) break; int ny = *itr; if (dist(x, y, nx, ny) < 100) { itr++; } else { if (ny <= y) itr++; else break; } } } } } // DEBUG_VEC(num); priority_queue, greater> pq; vector used(n); rep (i, n) { pii temp = xy[i]; if (x_flip) temp.first *= -1; if (y_flip) temp.second *= -1; if (rotate) { pii ntemp; ntemp.first = temp.first + temp.second; ntemp.second = temp.first - temp.second; temp = ntemp; } pq.push(temp); } int k = 0; vi ans; while (k * 90 < n) { if (pq.size() == 0) return false; pii xy = pq.top(); pq.pop(); if (rotate) { pii temp; temp.first = (xy.first + xy.second) / 2; temp.second = (xy.first - xy.second) / 2; xy = temp; } if (x_flip) xy.first *= -1; if (y_flip) xy.second *= -1; int idx = xy2i[xy]; if (used[idx]) continue; int x = xy.first, y = xy.second; if (x2y[x].count(y) == 0) continue; used[idx] = true; k++; ans.push_back(idx); vector era_xy; for (int add = -9; add <= 9; add++) { int nx = x + add; if (not in(nx, 0, 501)) continue; auto itr = x2y[nx].lower_bound(y - 9); while (true) { if (itr == x2y[nx].end()) break; int ny = *itr; if (dist(x, y, nx, ny) < 100) { x2y[nx].erase(itr); itr = x2y[nx].lower_bound(ny); era_xy.push_back(pii(nx, ny)); } else { if (ny <= y) itr++; else break; } } } } cout << k << endl; rep (i, ans.size()) cout << ans[i] + 1 << " "; cout << endl; return true; } signed main() { fio(); int n; cin >> n; vector> x2y(501); map xy2i; vector xy; rep (i, n) { int x, y; cin >> x >> y; x2y[x].insert(y); xy2i[pii(x, y)] = i; xy.push_back(pii(x, y)); } rep (i, 2) { rep (j, 2) { rep (k, 2) { if (solve2(n, x2y, xy2i, xy, i, j, k)) return 0; } } } // if (solve1(n, x2y, xy2i, xy)) return 0; }