Facebook
From Tacky Dove, 9 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 86
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. struct vertex
  9. {
  10.         int x;
  11.         int y;
  12. };
  13.  
  14. void input(vector<vertex>& p)
  15. {
  16.         int n;
  17.  
  18.         cin >> n;
  19.  
  20.         for (int i = 0; i < n; i++)
  21.         {
  22.                 vertex v;
  23.  
  24.                 cin >> v.x >> v.y;
  25.  
  26.                 p.push_back(v);
  27.         }
  28. }
  29.  
  30. long long cost(vertex v, vertex u, int diff)
  31. {
  32.         if (diff == 1) return 0;
  33.         return ((v.x - u.x) * (v.x - u.x) + (v.y - u.y) * (v.y - u.y));
  34. }
  35.  
  36. long long findingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r, int left, int right)
  37. {
  38.         if (r[left][right] != -1)
  39.                 return r[left][right];
  40.  
  41.         if (left - right == 1)
  42.                 return 0;
  43.  
  44.         long long x = 4000000000000000000;
  45.         int v = -1;     //z - ile razy ma siÄ™ wykonać  
  46.  
  47.         for (int k = left + 1; k < right; k++)
  48.         {
  49.                 long long n;
  50.  
  51.                 n = cost(p[left], p[k], left - right) + cost(p[k + 1], p[right], left - right) + findingDiagonals(p, d, r, left, k) + findingDiagonals(p, d, r, k + 1, right);
  52.  
  53.                 if (n < x)
  54.                 {
  55.                         x = n;
  56.                         v = k;
  57.                 }
  58.         }
  59.  
  60.         d[left][right] = v;
  61.         r[left][right] = x;
  62.  
  63.         return x;
  64. }
  65.  
  66. vertex choosingFirstDiagonal(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r)
  67. {
  68.         long long x = 4000000000000000000;
  69.         int minI, minJ;
  70.  
  71.         for (int i = 0; i < p.size() - 1; i++)
  72.                 for (int j = i + 1; j < p.size(); j++)
  73.                 {
  74.                         long long n;
  75.  
  76.                         n = cost(p[i], p[j], j - i) + findingDiagonals(p, d, r, i, j);
  77.  
  78.                         if (n < x)
  79.                         {
  80.                                 x = n;
  81.                                 minI = i;
  82.                                 minJ = j;
  83.                         }
  84.                 }
  85.  
  86.        
  87.  
  88.         vertex v;
  89.         v.x = minI;
  90.         v.y = minJ;
  91.  
  92.         return v;
  93. }
  94.  
  95. void choosingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vertex>& uD, vertex fD)
  96. {
  97.         if (fD.x - fD.y == 1)
  98.                 return;
  99.  
  100.         uD.push_back(fD);
  101.  
  102.         vertex u, v;
  103.  
  104.         u = v = fD;
  105.  
  106.         u.x = d[fD.x][fD.y];
  107.         v.y = d[fD.x][fD.y];
  108.  
  109.         choosingDiagonals(p, d, uD, u);
  110.         choosingDiagonals(p, d, uD, v);
  111. }
  112.  
  113. long long length(vector<vertex>& uD, vector<vector<long long>>& r)
  114. {
  115.         long long result = 0;
  116.  
  117.         for (auto i = uD.begin(); i != uD.end(); i++)
  118.                 result += r[(*i).x][(*i).y];
  119.  
  120.         return result;
  121. }
  122.  
  123. void output(vector<vertex>& uD, long long r)
  124. {
  125.         cout << r << " ";
  126.  
  127.         for (auto i = uD.begin(); i != uD.end(); i++)
  128.                 cout << (*i).x << " " << (*i).y << " ";
  129.  
  130.         cout << "\n";
  131. }
  132.  
  133. int main()
  134. {
  135.         ios_base::sync_with_stdio(0);
  136.  
  137.         int z;
  138.  
  139.         cin >> z;
  140.  
  141.         while (z--)
  142.         {
  143.                 vector<vertex> polygon;
  144.                 vector<vertex> usedDiagonals;
  145.                 vector<vector<int>> diagonals;
  146.                 vector<vector<long long>> results;
  147.                 long long result;
  148.  
  149.                 input(polygon);
  150.                 diagonals.assign(polygon.size() + 1, vector<int>(polygon.size() + 1, -1));
  151.                 results.assign(polygon.size() + 1, vector<long long>(polygon.size() + 1, -1));\
  152.  
  153.                 if (polygon.size() > 3)
  154.                 {
  155.                         vertex fDiag = choosingFirstDiagonal(polygon, diagonals, results);
  156.  
  157.                         choosingDiagonals(polygon, diagonals, usedDiagonals, fDiag);
  158.                 }
  159.  
  160.                 result = length(usedDiagonals, results);
  161.  
  162.                 output(usedDiagonals, result);
  163.         }
  164.  
  165.         return 0;
  166. }
  167.