#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)); priority_queue, greater> pq2; rep (i, n) pq2.push(xy[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; } 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)); } if (solve1(n, x2y, xy2i, xy)) return 0; else assert(false); // 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)); // priority_queue, greater> pq2; // rep (i, n) pq2.push(xy[i]); // int k = 0; // vi ans; // while (k * 90 < n) { // // if (pq.size() == 0) assert(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); // if (pq2.size() == 0) assert(false); // pii xy = pq2.top(); // pq.pop(); // 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; // } // } // } // 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; }