#include using namespace std; #define sz(x) ((int)x.size()) #define rep(i, a, b) for (int i = (a); i < (b); i++) #define all(x) begin(x), end(x) #define fi first #define se second typedef vector vi; typedef vector> vb; struct Maxclique { //double limit = 0.025, pk = 0; double limit = 0.025, pk = 0; struct Vertex { int i, d = 0; }; typedef vector vv; vb e; vv V; vector C; vi qmax, q, S, old; void init(vv& r) { for (auto& v : r) v.d = 0; for (auto& v : r) for (auto j : r) v.d += e[v.i][j.i]; sort(all(r), [](auto a, auto b) { return a.d > b.d; } ); int mxD = r[0].d; rep(i, 0, sz(r)) r[i].d = min(i, mxD) + 1; } void expand(vv& R, int lev = 1) { S[lev] += S[lev - 1] - old[lev]; old[lev] = S[lev - 1]; while (sz(R)) { if (sz(q) + R.back().d <= sz(qmax)) return; q.push_back(R.back().i); vv T; for (auto v : R) if (e[R.back().i][v.i]) T.push_back({v.i}); if (sz(T)) { if (S[lev]++ / ++pk < limit) init(T); int j = 0, mxk = 1, mnk = max(sz(qmax) - sz(q) + 1, 1); C[1].clear(), C[2].clear(); for (auto v : T) { int k = 1; auto f = [&](int i) { return e[v.i][i]; }; while (any_of(all(C[k]), f)) k++; if (k > mxk) mxk = k, C[mxk + 1].clear(); if (k < mnk) T[j++].i = v.i; C[k].push_back(v.i); } if (j > 0) T[j - 1].d = 0; rep(k, mnk, mxk + 1) for (int i : C[k]) T[j].i = i, T[j++].d = k; expand(T, lev + 1); } else if (sz(q) > sz(qmax)) qmax = q; q.pop_back(), R.pop_back(); } } vi maxClique() { init(V), expand(V); return qmax; } Maxclique(vb conn) : e(conn), C(sz(e) + 1), S(sz(C)), old(S) { rep(i, 0, sz(e)) V.push_back({i}); } }; double f(int x) { return sqrt(x) / 2; } vector, vector>> MEMO = { {{8, 1.41421}, {12,20,4,24,0,}}, {{9, 1.41421}, {20,17,3,34,6,30,}}, {{11, 1.11803}, {37,10,34,58,24,4,52,62,0,7,48,22,47,}}, {{11, 1.41421}, {37,42,24,19,5,1,56,60,23,55,}}, {{12, 1.41421}, {24,56,60,40,20,76,44,36,4,8,72,80,0,}}, {{14, 1.11803}, {92,46,51,19,14,74,97,23,99,83,65,78,37,5,28,0,112,106,120,55,115,60,42,69,10,}}, {{14, 1.41421}, {92,24,52,48,96,68,72,76,28,4,44,32,88,8,0,120,112,116,}}, {{15, 1.11803}, {74,29,66,117,34,122,126,24,99,136,38,1,15,89,103,80,71,132,96,57,60,140,94,20,6,43,52,131,11,}}, {{15, 1.41421}, {74,56,30,104,26,78,100,52,119,135,126,4,8,47,82,132,11,0,141,48,96,}}, {{16, 1.11803}, {42,99,96,150,50,107,141,34,7,116,18,45,27,158,3,143,52,88,23,91,61,126,168,72,118,80,0,161,77,165,134,69,12,123,}}, {{17, 1.11803}, {92,146,39,30,165,114,33,22,97,81,49,124,185,6,173,60,76,108,189,156,103,87,162,182,65,71,140,10,3,42,55,119,98,130,192,135,153,0,195,13,}}, {{17, 1.41421}, {91,162,39,143,102,151,95,35,5,185,72,61,125,140,98,31,42,181,182,132,121,1,65,69,192,188,9,13,}}, {{18, 1.11803}, {122,83,42,48,171,193,132,197,21,158,189,109,127,8,218,184,17,96,52,145,39,88,140,153,4,77,215,45,114,101,210,0,90,166,65,221,176,70,119,11,59,135,14,164,224,}}, {{18, 1.41421}, {122,174,82,42,102,182,50,46,178,6,154,18,78,38,214,142,186,206,146,210,0,224,110,218,10,150,134,90,114,70,14,74,}}, {{19, 1.41421}, {135,173,41,195,67,109,45,199,252,79,75,203,233,37,105,246,3,139,169,144,97,255,15,0,131,71,192,243,101,48,7,207,11,240,165,143,}}, {{20, 1.41421}, {148,104,176,76,216,36,240,248,244,116,252,44,48,12,204,84,280,276,212,208,284,220,152,8,40,172,184,80,108,288,16,272,144,140,112,136,180,4,72,0,68,}}, {{19, 1.11803}, {135,93,57,83,106,188,202,197,130,36,45,142,177,230,253,239,8,244,39,235,206,241,64,26,216,249,16,69,102,169,5,2,149,97,50,183,12,211,116,155,208,88,163,63,175,15,144,111,124,75,}}, {{20, 1.11803}, {149,93,250,90,112,105,209,206,229,215,176,144,125,140,55,46,23,220,276,65,19,137,102,152,271,273,117,286,238,264,185,33,14,8,283,279,170,43,51,70,11,235,182,163,84,98,173,244,58,241,79,196,4,0,}}, }; vi brute(int N, vb conn) { vi sol; for (int i = 0; i < N; i++) { bool ok = true; for (int j : sol) ok &= conn[i][j]; if (ok) sol.push_back(i); } return sol; } const double EPS = 1e-6; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; double r; cin >> n >> r; vector> nodes; for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) if (min({i, j, n - i, n - j}) >= r - EPS) nodes.push_back({i, j}); int N = nodes.size(); vb conn(N); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { int dx = abs(nodes[i].first - nodes[j].first); int dy = abs(nodes[i].second - nodes[j].second); if (dx * dx + dy * dy >= r * r * 4 - EPS) conn[i][j] = true; } vi sol; if (r > 1.5 + EPS) { sol = Maxclique(conn).maxClique(); } else if (r > f(4) + EPS && r <= f(5) + EPS) { for (auto& it : MEMO) { if (it.fi.fi == n && abs(it.fi.se - f(5)) < EPS) sol = it.se; } } else if (r > f(5) + EPS && r <= f(8) + EPS) { for (auto& it : MEMO) { if (it.fi.fi == n && abs(it.fi.se - f(8)) < EPS) sol = it.se; } } if (sol.empty()) sol = brute(N, conn); cout << sol.size() << '\n'; for (int i : sol) cout << nodes[i].first << ' ' << nodes[i].second << '\n'; }