SHARE
TWEET

Untitled

a guest Oct 13th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <random>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 100000;
  9. const int MAXN = 3001;
  10. int tries = 15000;
  11. int cnt = 100;
  12.  
  13. struct point{
  14.     int x, y;
  15.     double operator-(point& oth) {
  16.         return sqrt((x - oth.x) * (x - oth.x) + (y - oth.y) * (y - oth.y));
  17.     }
  18. };
  19.  
  20. point a[MAXN];
  21.  
  22. double get_dist(vector<int>& ind) {
  23.     double d = (a[0] - a[ind[0]]) + (a[ind.back()] - a[0]);
  24.     for (int i = 1; i < ind.size(); ++i) {
  25.         d += (a[ind[i]] - a[ind[i - 1]]);
  26.     }
  27.     return d;
  28. }
  29.  
  30. vector<int> v;
  31.  
  32. double get_mistakes() {
  33.     double d = (a[0] - a[v[0]]) + (a[v.back()] - a[0]);
  34.     for (int i = 1; i < v.size(); ++i) {
  35.         d += (a[v[i]] - a[v[i - 1]]);
  36.     }
  37.     return d;
  38. }
  39.  
  40. void reverse(int x, int y) {
  41.     int len = y - x + 1;
  42.     for (int i = x, cnt = 0; i < x + len/2; ++i, ++cnt) {
  43.         swap(v[i], v[y - cnt]);
  44.     }
  45. }
  46.  
  47. int main() {
  48.     std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  49.     srand(time(NULL));
  50.     int n;
  51.     cin >> n;
  52.     vector<int> start_state;
  53.     for (int i = 0; i < n; ++i) {
  54.         cin >> a[i].x >> a[i].y;
  55.         if (i > 0) {
  56.             start_state.push_back(i);
  57.         }
  58.     }
  59.     double energy = get_dist(start_state);
  60.     double start_energy = energy;
  61.     double temp = 20.0;
  62.  
  63.     double ans = energy;
  64.     vector<int> ans_vect;
  65.  
  66.     int sz = start_state.size();
  67.  
  68.     while (cnt--) {
  69.         v = start_state;
  70.  
  71.         for (int k = 1; k <= tries; k++) {
  72.  
  73.             int x = rand() % sz;
  74.             int y = rand() % sz;
  75.             while (x == y) {
  76.                 y = rand() % sz;
  77.             }
  78.             if (x > y) {
  79.                 swap(x, y);
  80.             }
  81.             reverse(x, y);
  82.  
  83.             double mistakes = get_mistakes();
  84.  
  85.             if (mistakes > energy) {
  86.                 double p = exp(-(mistakes - energy)/temp);
  87.                 if (p > 1.0 * (rand() % (INF + 1)) / INF) {
  88.                     energy = mistakes;
  89.                 } else {
  90.  
  91.                 }
  92.             }
  93.             energy = min(energy, mistakes);
  94.             temp = 0.99 * temp / k;
  95.             if (energy < ans) {
  96.                 ans = energy;
  97.                 ans_vect = v;
  98.             }
  99.         }
  100.         energy = start_energy;
  101.         temp = 20;
  102.     }
  103.     cout << "1 ";
  104.     for (auto x : ans_vect) {
  105.         cout << x + 1 << " ";
  106.     }
  107.     cout << 1;
  108.     return 0;
  109. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top