fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct P{int x,y;};
  4. double dist(const P &a,const P &b){double dx=a.x-b.x,dy=a.y-b.y;return sqrt(dx*dx+dy*dy);}
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int N,K;
  9.     if(!(cin>>N>>K)) return 0;
  10.     vector<P> pts(N);
  11.     for(int i=0;i<N;i++) cin>>pts[i].x>>pts[i].y;
  12.     const int GW=10, GH=14;
  13.     int cells = GW*GH;
  14.     vector<vector<int>> cluster(max(K,cells));
  15.     int MAXC=814000;
  16.     for(int i=0;i<N;i++){
  17.         int gx = (long long)pts[i].x * GW / (MAXC+1);
  18.         int gy = (long long)pts[i].y * GH / (MAXC+1);
  19.         if(gx<0) gx=0; if(gx>=GW) gx=GW-1;
  20.         if(gy<0) gy=0; if(gy>=GH) gy=GH-1;
  21.         int id = gy*GW + gx;
  22.         cluster[id].push_back(i);
  23.     }
  24.     if((int)cluster.size() < K) cluster.resize(K);
  25.     vector<int> emptyCells;
  26.     for(int i=0;i<cells;i++) if(cluster[i].empty()) emptyCells.push_back(i);
  27.     auto largest_idx = [&](void)->int{
  28.         int idx=-1, mx=-1;
  29.         for(int i=0;i<cells;i++){ if((int)cluster[i].size()>mx){mx=cluster[i].size(); idx=i;} }
  30.         return idx;
  31.     };
  32.     while(!emptyCells.empty()){
  33.         int to = emptyCells.back(); emptyCells.pop_back();
  34.         int from = largest_idx();
  35.         if(from==to) break;
  36.         if(cluster[from].size()<=1){
  37.             int found=-1;
  38.             for(int i=0;i<cells;i++) if((int)cluster[i].size()>1){ found=i; break;}
  39.             if(found==-1) break;
  40.             from=found;
  41.         }
  42.         int mv = cluster[from].back(); cluster[from].pop_back();
  43.         cluster[to].push_back(mv);
  44.     }
  45.     vector<vector<int>> tours(cells);
  46.     auto build_nn = [&](const vector<int>&pts_idx)->vector<int>{
  47.         int m = pts_idx.size();
  48.         if(m==0) return {};
  49.         vector<int> tour; tour.reserve(m);
  50.         vector<char> used(m,0);
  51.         int cur = 0;
  52.         tour.push_back(pts_idx[cur]);
  53.         used[cur]=1;
  54.         for(int t=1;t<m;t++){
  55.             int best=-1; double bd=1e300;
  56.             for(int j=0;j<m;j++) if(!used[j]){
  57.                 double d = dist(pts[ tour.back() ], pts[ pts_idx[j] ]);
  58.                 if(d<bd){ bd=d; best=j; }
  59.             }
  60.             used[best]=1;
  61.             tour.push_back(pts_idx[best]);
  62.         }
  63.         return tour;
  64.     };
  65.     auto tour_len = [&](const vector<int>&t)->double{
  66.         int m=t.size(); if(m==0) return 0.0;
  67.         double s=0;
  68.         for(int i=0;i<m;i++){
  69.             const P &a=pts[t[i]], &b=pts[t[(i+1)%m]];
  70.             s += dist(a,b);
  71.         }
  72.         return s;
  73.     };
  74.     auto run_2opt = [&](vector<int>&t, int iter_limit){
  75.         int n = t.size();
  76.         if(n<=2) return;
  77.         bool improved=true;
  78.         int iter=0;
  79.         while(improved && iter<iter_limit){
  80.             improved=false;
  81.             for(int i=0;i<n-1;i++){
  82.                 for(int j=i+2;j<n + (i>0?0:-1);j++){
  83.                     int a=i, b=(i+1)%n, c=j%n, d=(j+1)%n;
  84.                     double before = dist(pts[t[a]],pts[t[b]]) + dist(pts[t[c]],pts[t[d]]);
  85.                     double after = dist(pts[t[a]],pts[t[c]]) + dist(pts[t[b]],pts[t[d]]);
  86.                     if(after + 1e-12 < before){
  87.                         if(a < c){
  88.                             reverse(t.begin()+b, t.begin()+c+1);
  89.                         } else {
  90.                             vector<int> nt;
  91.                             for(int k=0;k<=a;k++) nt.push_back(t[k]);
  92.                             for(int k=c;k>=b;k--) nt.push_back(t[k]);
  93.                             for(int k=a+1;k<=c-1;k++) nt.push_back(t[k]);
  94.                             t.swap(nt);
  95.                         }
  96.                         improved=true;
  97.                         goto NEXT;
  98.                     }
  99.                 }
  100.             }
  101.             NEXT:
  102.             iter++;
  103.         }
  104.     };
  105.     for(int i=0;i<cells;i++){
  106.         tours[i] = build_nn(cluster[i]);
  107.         if(tours[i].size()>1) run_2opt(tours[i], 200);
  108.     }
  109.     vector<double> len(cells);
  110.     for(int i=0;i<cells;i++) len[i]=tour_len(tours[i]);
  111.     auto neighbors = [&](int id)->vector<int>{
  112.         int gx = id % GW;
  113.         int gy = id / GW;
  114.         vector<int> res;
  115.         for(int dx=-1;dx<=1;dx++) for(int dy=-1;dy<=1;dy++){
  116.             if(dx==0 && dy==0) continue;
  117.             int nx=gx+dx, ny=gy+dy;
  118.             if(nx>=0 && nx<GW && ny>=0 && ny<GH) ;
  119.         }
  120.         res.clear();
  121.         for(int dy=-1;dy<=1;dy++) for(int dx=-1;dx<=1;dx++){
  122.             if(dx==0 && dy==0) continue;
  123.             int nx = gx+dx, ny = gy+dy;
  124.             if(nx>=0 && nx< GW && ny>=0 && ny<GH) res.push_back(ny*GW+nx);
  125.         }
  126.         return res;
  127.     };
  128.     for(int iter=0; iter<200; iter++){
  129.         int worst = max_element(len.begin(), len.end()) - len.begin();
  130.         vector<int> nbs = neighbors(worst);
  131.         double bestgain = 1e-12;
  132.         int pick_from=-1, pick_to=-1, pick_pos=-1;
  133.         for(int nb : nbs){
  134.             if(nb<0 || nb>=cells) continue;
  135.             for(int idxPos=0; idxPos<(int)tours[worst].size(); idxPos++){
  136.                 int city = tours[worst][idxPos];
  137.                 int prev = tours[worst][ (idxPos-1 + tours[worst].size())%tours[worst].size() ];
  138.                 int next = tours[worst][ (idxPos+1) % tours[worst].size() ];
  139.                 double removeCost = dist(pts[prev], pts[city]) + dist(pts[city], pts[next]) - dist(pts[prev], pts[next]);
  140.                 double bestInsert = 1e300;
  141.                 int bestI = -1;
  142.                 int m = tours[nb].size();
  143.                 if(m==0){
  144.                     bestInsert = 2*0.0;
  145.                     bestI = 0;
  146.                 } else {
  147.                     for(int j=0;j<m;j++){
  148.                         int a = tours[nb][j];
  149.                         int b = tours[nb][ (j+1)%m ];
  150.                         double ins = dist(pts[a], pts[city]) + dist(pts[city], pts[b]) - dist(pts[a], pts[b]);
  151.                         if(ins < bestInsert){ bestInsert = ins; bestI = j+1; }
  152.                     }
  153.                 }
  154.                 double newWorstLen = len[worst] - removeCost;
  155.                 double newNbLen = len[nb] + bestInsert;
  156.                 double newMax = newWorstLen;
  157.                 if(newNbLen > newMax) newMax = newNbLen;
  158.                 double oldMax = max(len[worst], len[nb]);
  159.                 double gain = oldMax - newMax;
  160.                 if(gain > bestgain){
  161.                     bestgain = gain;
  162.                     pick_from = idxPos;
  163.                     pick_to = nb;
  164.                     pick_pos = bestI;
  165.                 }
  166.             }
  167.         }
  168.         if(pick_from==-1) break;
  169.         int city = tours[worst][pick_from];
  170.         tours[worst].erase(tours[worst].begin()+pick_from);
  171.         if(pick_pos > (int)tours[pick_to].size()) pick_pos = tours[pick_to].size();
  172.         tours[pick_to].insert(tours[pick_to].begin()+pick_pos, city);
  173.         len[worst]=tour_len(tours[worst]);
  174.         len[pick_to]=tour_len(tours[pick_to]);
  175.         if(tours[worst].size()>1) run_2opt(tours[worst], 60);
  176.         if(tours[pick_to].size()>1) run_2opt(tours[pick_to], 60);
  177.         len[worst]=tour_len(tours[worst]);
  178.         len[pick_to]=tour_len(tours[pick_to]);
  179.     }
  180.     for(int i=0;i<K;i++){
  181.         if(i < cells){
  182.             int m = tours[i].size();
  183.             cout<<m;
  184.             for(int j=0;j<m;j++) cout<<" "<<(tours[i][j]+1);
  185.             cout<<"\n";
  186.         } else {
  187.             cout<<"1 "<<1<<"\n";
  188.         }
  189.     }
  190.     return 0;
  191. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
3 2
0 0
3 0
3 1
stdout 
1 1
0
https://ideone.com/zk3Zkw
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!