fork download
copy 
  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 = double(a.x)-double(b.x);
  6.     double dy = double(a.y)-double(b.y);
  7.     return sqrt(dx*dx + dy*dy);
  8. }
  9. int main(){
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     int N, K;
  13.     if(!(cin>>N>>K)) return 0;
  14.     vector<P> pts(N);
  15.     for(int i=0;i<N;i++) cin>>pts[i].x>>pts[i].y;
  16.  
  17.     // grid (문제에 맞춰 10x14 = 140)
  18.     const int GW = 10, GH = 14;
  19.     const int CELLS = GW * GH; // 140
  20.     vector<vector<int>> cluster(CELLS);
  21.     const int MAXC = 814000;
  22.     for(int i=0;i<N;i++){
  23.         int gx = (long long)pts[i].x * GW / (MAXC+1);
  24.         int gy = (long long)pts[i].y * GH / (MAXC+1);
  25.         gx = max(0, min(GW-1, gx));
  26.         gy = max(0, min(GH-1, gy));
  27.         int id = gy*GW + gx;
  28.         cluster[id].push_back(i);
  29.     }
  30.  
  31.     // 빈 셀 채우기: 가장 큰 셀에서 하나씩 옮김
  32.     vector<int> emptyCells;
  33.     for(int i=0;i<CELLS;i++) if(cluster[i].empty()) emptyCells.push_back(i);
  34.     auto largest_idx = [&]()->int{
  35.         int idx = 0; int mx = cluster[0].size();
  36.         for(int i=1;i<CELLS;i++) if((int)cluster[i].size() > mx){ mx = cluster[i].size(); idx = i; }
  37.         return idx;
  38.     };
  39.     while(!emptyCells.empty()){
  40.         int to = emptyCells.back();
  41.         int from = largest_idx();
  42.         if(from==to) break;
  43.         if(cluster[from].size()<=1){
  44.             int found=-1;
  45.             for(int i=0;i<CELLS;i++) if(cluster[i].size()>1){ found=i; break; }
  46.             if(found==-1) break;
  47.             from = found;
  48.         }
  49.         int mv = cluster[from].back();
  50.         cluster[from].pop_back();
  51.         cluster[to].push_back(mv);
  52.         emptyCells.pop_back();
  53.     }
  54.  
  55.     // nearest-neighbor 초기화 (O(m^2) per cluster)
  56.     auto build_nn = [&](const vector<int>& idxs)->vector<int>{
  57.         int m = idxs.size();
  58.         if(m==0) return {};
  59.         vector<int> tour; tour.reserve(m);
  60.         vector<char> used(m,0);
  61.         int cur = 0;
  62.         tour.push_back(idxs[cur]);
  63.         used[cur]=1;
  64.         for(int step=1; step<m; step++){
  65.             int best = -1; double bd = 1e300;
  66.             for(int j=0;j<m;j++) if(!used[j]){
  67.                 double d = dist( pts[tour.back()], pts[idxs[j]] );
  68.                 if(d < bd){ bd = d; best = j; }
  69.             }
  70.             used[best]=1;
  71.             tour.push_back(idxs[best]);
  72.         }
  73.         return tour;
  74.     };
  75.  
  76.     // 안정적인 2-opt (표준 구현)
  77.     auto tour_len = [&](const vector<int>& t)->double{
  78.         int m = t.size();
  79.         if(m<=1) return 0.0;
  80.         double s=0;
  81.         for(int i=0;i<m;i++){
  82.             s += dist( pts[t[i]], pts[t[(i+1)%m]] );
  83.         }
  84.         return s;
  85.     };
  86.     auto two_opt = [&](vector<int>& t, int iter_limit){
  87.         int n = t.size();
  88.         if(n<=2) return;
  89.         bool improved = true;
  90.         int it = 0;
  91.         while(improved && it < iter_limit){
  92.             improved = false;
  93.             for(int i=0;i<n-1;i++){
  94.                 for(int j=i+2;j<n;j++){
  95.                     if(i==0 && j==n-1) continue; // 전체 루프를 깨는 교체 방지
  96.                     double before = dist(pts[t[i]], pts[t[(i+1)%n]]) + dist(pts[t[j]], pts[t[(j+1)%n]]);
  97.                     double after  = dist(pts[t[i]], pts[t[j]]) + dist(pts[t[(i+1)%n]], pts[t[(j+1)%n]]);
  98.                     if(after + 1e-12 < before){
  99.                         reverse(t.begin() + (i+1), t.begin() + (j+1));
  100.                         improved = true;
  101.                         goto NEXT_ITER;
  102.                     }
  103.                 }
  104.             }
  105.             NEXT_ITER:
  106.             it++;
  107.         }
  108.     };
  109.  
  110.     // 초기 tours 구성
  111.     vector<vector<int>> tours(CELLS);
  112.     for(int i=0;i<CELLS;i++){
  113.         tours[i] = build_nn(cluster[i]);
  114.         if(tours[i].size()>1) two_opt(tours[i], 200);
  115.     }
  116.     vector<double> len(CELLS);
  117.     for(int i=0;i<CELLS;i++) len[i] = tour_len(tours[i]);
  118.  
  119.     // 인접 셀 반환
  120.     auto neighbors = [&](int id)->vector<int>{
  121.         vector<int> res;
  122.         if(id < 0 || id >= CELLS) return res;
  123.         int gx = id % GW, gy = id / GW;
  124.         for(int dy=-1; dy<=1; dy++) for(int dx=-1; dx<=1; dx++){
  125.             if(dx==0 && dy==0) continue;
  126.             int nx = gx + dx, ny = gy + dy;
  127.             if(nx>=0 && nx < GW && ny>=0 && ny < GH) res.push_back(ny*GW + nx);
  128.         }
  129.         return res;
  130.     };
  131.  
  132.     // 개선 루프: 최대 경로(worst cluster)에서 주변으로 도시 이동 시도
  133.     for(int iter=0; iter<250; iter++){
  134.         int worst = max_element(len.begin(), len.end()) - len.begin();
  135.         vector<int> nbs = neighbors(worst);
  136.         double bestgain = 1e-12;
  137.         int best_from_pos=-1, best_to_cell=-1, best_to_insert_pos=-1;
  138.         for(int nb : nbs){
  139.             if(nb<0 || nb>=CELLS) continue;
  140.             int m_w = tours[worst].size();
  141.             if(m_w==0) continue;
  142.             for(int pos=0; pos<m_w; pos++){
  143.                 int city = tours[worst][pos];
  144.                 int prev = tours[worst][ (pos-1 + m_w) % m_w ];
  145.                 int next = tours[worst][ (pos+1) % m_w ];
  146.                 double removeCost = dist(pts[prev], pts[city]) + dist(pts[city], pts[next]) - dist(pts[prev], pts[next]);
  147.                 double bestInsert = 1e300;
  148.                 int bestI = 0;
  149.                 int m_nb = tours[nb].size();
  150.                 if(m_nb==0){
  151.                     // insert into empty nb: cost = 0 -> cycle of length 0 becomes two edges city->city (effectively 0)
  152.                     bestInsert = 0.0;
  153.                     bestI = 0;
  154.                 } else {
  155.                     for(int j=0;j<m_nb;j++){
  156.                         int a = tours[nb][j];
  157.                         int b = tours[nb][ (j+1)%m_nb ];
  158.                         double ins = dist(pts[a], pts[city]) + dist(pts[city], pts[b]) - dist(pts[a], pts[b]);
  159.                         if(ins < bestInsert){ bestInsert = ins; bestI = j+1; }
  160.                     }
  161.                 }
  162.                 double newWorstLen = len[worst] - removeCost;
  163.                 double newNbLen = len[nb] + bestInsert;
  164.                 double newMax = max(newWorstLen, newNbLen);
  165.                 double oldMax = max(len[worst], len[nb]);
  166.                 double gain = oldMax - newMax;
  167.                 if(gain > bestgain){
  168.                     bestgain = gain;
  169.                     best_from_pos = pos;
  170.                     best_to_cell = nb;
  171.                     best_to_insert_pos = bestI;
  172.                 }
  173.             }
  174.         }
  175.         if(best_from_pos == -1) break;
  176.         // 수행
  177.         int city = tours[worst][best_from_pos];
  178.         tours[worst].erase(tours[worst].begin() + best_from_pos);
  179.         if(best_to_insert_pos > (int)tours[best_to_cell].size()) best_to_insert_pos = tours[best_to_cell].size();
  180.         tours[best_to_cell].insert(tours[best_to_cell].begin() + best_to_insert_pos, city);
  181.         if(tours[worst].size()>1) two_opt(tours[worst], 60);
  182.         if(tours[best_to_cell].size()>1) two_opt(tours[best_to_cell], 60);
  183.         len[worst] = tour_len(tours[worst]);
  184.         len[best_to_cell] = tour_len(tours[best_to_cell]);
  185.     }
  186.  
  187.     // 출력 전 보정: 처음 K개의 슬롯이 모두 1개 이상을 가지도록 함
  188.     // (문제의 K==CELLS인 경우 이 단계에서 모두 채워져야 함)
  189.     vector<int> empties;
  190.     for(int i=0;i<K;i++) if(i < (int)tours.size() && tours[i].empty()) empties.push_back(i);
  191.     for(int e : empties){
  192.         int donor = -1, mx = 0;
  193.         for(int j=0;j<K;j++){
  194.             if(j < (int)tours.size() && (int)tours[j].size() > mx){
  195.                 mx = tours[j].size(); donor = j;
  196.             }
  197.         }
  198.         if(donor==-1 || mx<=1) break;
  199.         int mv = tours[donor].back(); tours[donor].pop_back();
  200.         tours[e].push_back(mv);
  201.     }
  202.  
  203.     // 중복/누락 검사: 실패 시 안전한 분배(라운드로빈)로 폴백
  204.     vector<char> seen(N,false);
  205.     bool ok = true;
  206.     for(int i=0;i<K && i<(int)tours.size(); i++){
  207.         for(int c : tours[i]){
  208.             if(c<0 || c>=N){ ok=false; break; }
  209.             if(seen[c]){ ok=false; break; }
  210.             seen[c]=true;
  211.         }
  212.         if(!ok) break;
  213.     }
  214.     for(int i=0;i<N;i++) if(!seen[i]){ ok=false; break; }
  215.     if(!ok){
  216.         // 폴백: 간단히 라운드로빈으로 분배
  217.         vector<vector<int>> fallback(K);
  218.         for(int i=0;i<N;i++) fallback[i%K].push_back(i);
  219.         for(int i=0;i<K;i++) tours[i] = fallback[i];
  220.     }
  221.  
  222.     // 최종 출력: K줄 (1-based index)
  223.     for(int i=0;i<K;i++){
  224.         if(i < (int)tours.size()){
  225.             cout << tours[i].size();
  226.             for(int v : tours[i]) cout << ' ' << (v+1);
  227.             cout << '\n';
  228.         } else {
  229.             // 잘못된 상황 방어 (보통 발생하지 않음)
  230.             cout << "1 1\n";
  231.         }
  232.     }
  233.     return 0;
  234. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3 2
0 0
3 0
3 1
stdout
copy 
2 1 3
1 2
https://ideone.com/MnbjNa
language:
C++ (gcc 8.3)
created:
9 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!