#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template string in_v_to_str (const pair v); template string v_to_str (const pair v); string in_v_to_str (const char v) { return "'" + string{v} + "'"; } string in_v_to_str (const char* v) { return "\"" + string(v) + "\""; } string in_v_to_str (const string v) { return "\"" + v + "\""; } template string in_v_to_str (const T v) { stringstream ss; ss << v; return ss.str(); } template string v_to_str (const T v) { stringstream ss; ss << v; return ss.str(); } template string v_to_str (const array& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (size_t i = 0; i < v.size() - 1; ++i) { ss << in_v_to_str(v[i]) << ", "; } ss << in_v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[]"; } return ss.str(); } template string v_to_str (const array< array, N >& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (size_t i = 0; i < v.size() - 1; ++i) { ss << v_to_str(v[i]) << ", "; } ss << v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[-]"; } return ss.str(); } template string v_to_str (const vector& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (size_t i = 0; i < v.size() - 1; ++i) { ss << in_v_to_str(v[i]) << ", "; } ss << in_v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[]"; } return ss.str(); } template string v_to_str (const vector< vector >& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (size_t i = 0; i < v.size() - 1; ++i) { ss << v_to_str(v[i]) << ", "; } ss << v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[-]"; } return ss.str(); } template string v_to_str (const set& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i) << (len-- > 1 ? ", " : "}"); } return ss.str(); } template string v_to_str (const map& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i.first) << " : " << in_v_to_str(i.second) << (len-- > 1 ? ", " : "}"); } return ss.str(); } template string v_to_str (const unordered_set& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i) << (len-- > 1 ? ", " : "}"); } return ss.str(); } template string v_to_str (const unordered_map& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i.first) << " : " << in_v_to_str(i.second) << (len-- > 1 ? ", " : "}"); } return ss.str(); } template string in_v_to_str (const pair v) { stringstream ss; ss << "<" << v_to_str(v.first) << ", " << v_to_str(v.second) << ">"; return ss.str(); } template string v_to_str (const pair v) { stringstream ss; ss << "<" << v_to_str(v.first) << ", " << v_to_str(v.second) << ">"; return ss.str(); } string print () { return ""; } template string print (const F& f, const R& ...r) { stringstream ss; ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); } return ss.str(); } template void pdebug (const F& f, const R& ...r) { stringstream ss; ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); } cerr << "" << ss.str() << "" << endl; } template void fdebug (const F& f, const R& ...r) { stringstream ss; ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); } cerr << "" << ss.str() << "" << endl; } template void tdebug (const F& f, const R& ...r) { stringstream ss; ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); } cerr << "[time]" << ss.str() << "" << endl; } struct e512pos { public: int x; int y; e512pos () { this->x = 0; this->y = 0; } e512pos (int x, int y) { this->x = x; this->y = y; } e512pos operator + (const e512pos& t) { return e512pos(this->x + t.x, this->y + t.y); } e512pos operator - (const e512pos& t) { return e512pos(this->x - t.x, this->y - t.y); } bool operator == (const e512pos& t) const { return this->x == t.x && this->y == t.y; } }; namespace std { template <> class hash { public: size_t operator()(const e512pos& t) const{ return t.x<<16 | t.y; } }; } ostream& operator << (ostream& os, const e512pos& p) { os << "(" << p.x << ", " << p.y << ")"; return os; }; class StopWatch { public: std::chrono::system_clock::time_point start, tstart, end; StopWatch () { this->start = std::chrono::system_clock::now(); } inline void stop () { this->tstart = std::chrono::system_clock::now(); } inline void resume () { this->start += std::chrono::system_clock::now() - this->tstart; } inline uint64_t get_milli_time () { this->end = std::chrono::system_clock::now(); return std::chrono::duration_cast(end-start).count(); } }; inline uint32_t xrnd() { static uint32_t y = 2463534242; y = y ^ (y << 13); y = y ^ (y >> 17); return y = y ^ (y << 5); } inline float distance (const e512pos& a, const e512pos& b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } class MM { public: StopWatch sw; int N, M; vector planet; vector best; bitset<256> bestm; MM () { this->sw = StopWatch(); } void input () { cin >> this->N >> this->M; for (int i = 0; i < 256; ++i) { this->planet.emplace_back(0, 0); } for (int i = 0; i < this->N; ++i) { cin >> this->planet[i].x >> this->planet[i].y; } } void output0 () { for (int i = 0; i < this->M; ++i) { cout << print(0, i+1) << endl; } cout << this->best.size() + 2 << endl; cout << print(1, 1) << endl; for (int i = 0; i < this->best.size(); ++i) { cout << print(1, this->best[i]+1) << endl; } cout << print(1, 1) << endl; for (int i = 0; i < this->M; ++i) { this->bestm[i] = true; } // pdebug((int)(1000000000 / (1000+sqrt(this->allscore(this->best))))); } void output () { for (int i = 0; i < this->M; ++i) { this->bestm[i] = true; } vector mindex; for (int i = 0; i < 256; ++i) { mindex.emplace_back(0); } int cnt = 0; for (int i = 0; i < this->N; ++i) { if (this->bestm[i]) { cout << print(this->planet[i].x, this->planet[i].y) << endl; mindex[this->bestm[i]] = cnt; cnt += 1; } } vector< pair > out; int p = 0; out.emplace_back(1, 0); if (this->bestm[0]) { out.emplace_back(2, mindex[0]); } for (auto&& i : this->best) { if (this->bestm[i]) { out.emplace_back(2, mindex[i]); } out.emplace_back(1, i); if (this->bestm[i]) { out.emplace_back(2, mindex[i]); } p = i; } if (this->bestm[0]) { out.emplace_back(2, mindex[0]); } out.emplace_back(1, 0); cout << out.size() << endl; for (auto&& i : out) { cout << print(i.first, i.second+1) << endl; } } void solve () { vector v; e512pos p = this->planet[0]; bitset<256> use; use[0] = true; for (int z = 0; z < this->N-1; ++z) { int best = -1; float bestdist = 1000000000; for (int i = 1; i < this->N; ++i) { if (use[i]) { continue; } int x = (p.x - this->planet[i].x); int y = (p.y - this->planet[i].y); float dist = sqrt(x*x+y*y); if (dist < bestdist) { bestdist = dist; best = i; } } use[best] = true; v.emplace_back(best); p = this->planet[best]; } this->best = v; } // float mallscore (vector< pair >& bitset<256> m) { // float r = 0; // int p = 0; // int t = 1; // for (int i = 0; i < this->N; ++i) { // float d = distance(this->planet[p], this->planet[v[i].second]); // if (m[p] || m[v[i].second]) { // r += d*d*5; // } else { // r += d*d*25; // } // t = v[i].first; // p = v[i].second; // } // float d = distance(this->planet[p], this->planet[0]); // r += d*d*mat[t][0]; // if (m[p] || m[0]) { // r += d*d*5; // } else { // r += d*d*25; // } // return r; // } }; int main () { cin.tie(0); ios::sync_with_stdio(false); MM mm; mm.input(); mm.solve(); mm.output(); cout.flush(); return 0; }