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