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){
  5.     double dx=a.x-b.x, dy=a.y-b.y;
  6.     return sqrt(dx*dx+dy*dy);
  7. }
  8. int main(){
  9.     ios::sync_with_stdio(false); cin.tie(nullptr);
  10.     int N,K; cin>>N>>K;
  11.     vector<P> pts(N);
  12.     for(int i=0;i<N;i++) cin>>pts[i].x>>pts[i].y;
  13.     const int GW=10, GH=14, CELLS=GW*GH, MAXC=814000;
  14.     vector<vector<int>> cluster(CELLS);
  15.     for(int i=0;i<N;i++){
  16.         int gx = (long long)pts[i].x*GW/(MAXC+1);
  17.         int gy = (long long)pts[i].y*GH/(MAXC+1);
  18.         gx=max(0,min(GW-1,gx)); gy=max(0,min(GH-1,gy));
  19.         cluster[gy*GW+gx].push_back(i);
  20.     }
  21.     vector<int> empty;
  22.     for(int i=0;i<CELLS;i++) if(cluster[i].empty()) empty.push_back(i);
  23.     auto largest_idx=[&]()->int{
  24.         int mx=0, idx=0;
  25.         for(int i=0;i<CELLS;i++) if(cluster[i].size()>mx){ mx=cluster[i].size(); idx=i; }
  26.         return idx;
  27.     };
  28.     while(!empty.empty()){
  29.         int to=empty.back(), from=largest_idx();
  30.         if(from==to) break;
  31.         if(cluster[from].size()<=1){ empty.pop_back(); continue; }
  32.         cluster[to].push_back(cluster[from].back());
  33.         cluster[from].pop_back();
  34.         empty.pop_back();
  35.     }
  36.     auto build_nn=[&](const vector<int>& idxs)->vector<int>{
  37.         int m=idxs.size(); if(m==0) return {};
  38.         vector<int> tour; tour.reserve(m);
  39.         vector<char> used(m,0);
  40.         int cur=0; tour.push_back(idxs[cur]); used[cur]=1;
  41.         for(int step=1;step<m;step++){
  42.             int best=-1; double bd=1e300;
  43.             for(int j=0;j<m;j++) if(!used[j]){
  44.                 double d=dist(pts[tour.back()], pts[idxs[j]]);
  45.                 if(d<bd){ bd=d; best=j; }
  46.             }
  47.             used[best]=1; tour.push_back(idxs[best]);
  48.         }
  49.         return tour;
  50.     };
  51.     auto tour_len=[&](const vector<int>& t)->double{
  52.         int m=t.size(); if(m<=1) return 0.0;
  53.         double s=0; for(int i=0;i<m;i++) s+=dist(pts[t[i]], pts[t[(i+1)%m]]);
  54.         return s;
  55.     };
  56.     auto two_opt=[&](vector<int>& t,int iter_limit){
  57.         int n=t.size(); if(n<=2) return;
  58.         bool improved=true; int it=0;
  59.         while(improved && it<iter_limit){
  60.             improved=false;
  61.             for(int i=0;i<n-1;i++){
  62.                 for(int j=i+2;j<n;j++){
  63.                     if(i==0 && j==n-1) continue;
  64.                     double before=dist(pts[t[i]],pts[t[i+1]])+dist(pts[t[j]],pts[t[(j+1)%n]]);
  65.                     double after=dist(pts[t[i]],pts[t[j]])+dist(pts[t[i+1]],pts[t[(j+1)%n]]);
  66.                     if(after+1e-12<before){ reverse(t.begin()+i+1, t.begin()+j+1); improved=true; goto NEXT; }
  67.                 }
  68.             }
  69.             NEXT: it++;
  70.         }
  71.     };
  72.     vector<vector<int>> tours(CELLS);
  73.     for(int i=0;i<CELLS;i++){ tours[i]=build_nn(cluster[i]); if(tours[i].size()>1) two_opt(tours[i],200); }
  74.     vector<double> len(CELLS); for(int i=0;i<CELLS;i++) len[i]=tour_len(tours[i]);
  75.     auto neighbors=[&](int id)->vector<int>{
  76.         vector<int> res; int gx=id%GW, gy=id/GW;
  77.         for(int dy=-1;dy<=1;dy++) for(int dx=-1;dx<=1;dx++){
  78.             if(dx==0 && dy==0) continue;
  79.             int nx=gx+dx, ny=gy+dy;
  80.             if(nx>=0 && nx<GW && ny>=0 && ny<GH) res.push_back(ny*GW+nx);
  81.         } return res;
  82.     };
  83.     for(int iter=0;iter<250;iter++){
  84.         int worst=max_element(len.begin(),len.end())-len.begin();
  85.         vector<int> nbs=neighbors(worst); double bestgain=1e-12;
  86.         int best_from=-1,best_to=-1,best_pos=-1;
  87.         for(int nb:nbs){
  88.             if(nb<0 || nb>=CELLS) continue;
  89.             int m_w=tours[worst].size(); if(m_w==0) continue;
  90.             for(int pos=0;pos<m_w;pos++){
  91.                 int city=tours[worst][pos];
  92.                 int prev=tours[worst][(pos-1+m_w)%m_w], next=tours[worst][(pos+1)%m_w];
  93.                 double removeCost=dist(pts[prev],pts[city])+dist(pts[city],pts[next])-dist(pts[prev],pts[next]);
  94.                 double bestInsert=1e300; int bestI=0;
  95.                 int m_nb=tours[nb].size();
  96.                 if(m_nb==0){ bestInsert=0.0; bestI=0; }
  97.                 else for(int j=0;j<m_nb;j++){
  98.                     int a=tours[nb][j], b=tours[nb][(j+1)%m_nb];
  99.                     double ins=dist(pts[a],pts[city])+dist(pts[city],pts[b])-dist(pts[a],pts[b]);
  100.                     if(ins<bestInsert){ bestInsert=ins; bestI=j+1; }
  101.                 }
  102.                 double newWorst=len[worst]-removeCost;
  103.                 double newNb=len[nb]+bestInsert;
  104.                 double newMax=max(newWorst,newNb), oldMax=max(len[worst],len[nb]);
  105.                 double gain=oldMax-newMax;
  106.                 if(gain>bestgain){ bestgain=gain; best_from=pos; best_to=nb; best_pos=bestI; }
  107.             }
  108.         }
  109.         if(best_from==-1) break;
  110.         int city=tours[worst][best_from]; tours[worst].erase(tours[worst].begin()+best_from);
  111.         if(best_pos>(int)tours[best_to].size()) best_pos=tours[best_to].size();
  112.         tours[best_to].insert(tours[best_to].begin()+best_pos, city);
  113.         if(tours[worst].size()>1) two_opt(tours[worst],60);
  114.         if(tours[best_to].size()>1) two_opt(tours[best_to],60);
  115.         len[worst]=tour_len(tours[worst]); len[best_to]=tour_len(tours[best_to]);
  116.     }
  117.     for(int i=0;i<K;i++){
  118.         if(i<(int)tours.size()){
  119.             cout<<tours[i].size();
  120.             for(int v:tours[i]) cout<<" "<<v+1;
  121.             cout<<"\n";
  122.         } else cout<<"1 1\n";
  123.     }
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
3 2
0 0
3 0
3 1
stdout 
1 1
0
https://ideone.com/3Gww6r
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!