Advertisement
he_obviously

lshkn_highways

Apr 24th, 2020
496
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.19 KB | None | 0 0
  1. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  2. //#pragma GCC optimize("unroll-loops")
  3. //#pragma GCC optimize("Ofast")
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. #define pb push_back
  12. #define pii pair<int, int>
  13. #define mp make_pair
  14. #define loop(i, n) for(int i = 0; i < (int)n; ++i)
  15. #define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
  16. #define rloop(i, n) for (int i = (int)n; i >= 0; --i)
  17. #define F first
  18. #define S second
  19. #define sorted(a) sort(a.begin(), a.end())
  20.  
  21. const long double EPS = 1e-9;
  22.  
  23. struct Point {
  24.     long double x; long double y;
  25. };
  26.  
  27. Point make_point(long double x, long double y) {
  28.     Point a;
  29.     a.x = x; a.y = y;
  30.     return a;
  31. }
  32.  
  33. vector <vector <Point>> highways;
  34. vector <int> weights;
  35. Point office;
  36. int n, w;
  37. long double x, y;
  38.  
  39. void optimize(Point cur) {
  40.     cur.x = cur.x - office.x;
  41.     cur.y = cur.y - office.y;
  42. }
  43.  
  44. void read () {
  45.     cin >> n >> w >> x >> y;
  46.     office = make_point(x, y);
  47.     highways.resize(n);
  48.     weights.resize(n);
  49.     for (int i = 0; i < n; ++i) {
  50.         int k, p;
  51.         cin >> k >> p;
  52.         weights[i] = p;
  53.         highways[i].resize(k);
  54.         for (int j = 0; j < k; ++j) {
  55.             long double xi, yi;
  56.             cin >> xi >> yi;
  57.             highways[i][j] = make_point(xi, yi);
  58.             optimize(highways[i][j]);
  59.         }
  60.     }
  61.     office = make_point(0, 0);
  62. }
  63.  
  64. int total() {
  65.     int ans = 0;
  66.     for (int weight : weights) {
  67.         ans += weight;
  68.     }
  69.     return ans;
  70. }
  71.  
  72. long double sqr(long double a) {
  73.     return a * a;
  74. }
  75.  
  76. double to_office(Point a) {
  77.     long double x = a.x;
  78.     long double y = a.y;
  79.     return x * x + y * y;
  80. }
  81.  
  82. long double find_normal(Point a, Point b) {
  83.     Point left = a;
  84.     Point right = make_point(b.x + EPS, b.y + EPS);
  85.     while (fabs(left.x - right.x) > EPS || fabs(left.y - right.y) > EPS) {
  86.         Point m1 = make_point(left.x + (right.x - left.x) / 3, left.y + (right.y - left.y) / 3);
  87.         Point m2 = make_point(right.x - (right.x - left.x) / 3, right.y - (right.y - left.y) / 3);
  88.         if (to_office(m1) > to_office(m2)) {
  89.             left.x = m1.x;
  90.             left.y = m1.y;
  91.         }
  92.         else {
  93.             right.x = m2.x;
  94.             right.y = m2.y;
  95.         }
  96.     }
  97.     return to_office(left);
  98. }
  99.  
  100. long double find_optimal(int i) {
  101.     long double answer = 1e9;
  102.     for (int j = 0; j < (int)highways[i].size(); ++j) {
  103.         long double to_point = to_office(highways[i][j]);
  104.         answer = min(answer, to_point);
  105.     }
  106.     for (int j = 0; j < (int)highways[i].size() - 1; ++j) {
  107.         Point a = highways[i][j];
  108.         Point b = highways[i][j + 1];
  109.         long double normal = find_normal(a, b);
  110.         answer = min(answer, normal);
  111.     }
  112.     return sqrt(answer);
  113. }
  114.  
  115. int main() {
  116.     ios::sync_with_stdio(0);
  117.     cin.tie(0); cout.tie(0);
  118.     int t; cin >> t;
  119.     for (int test = 0; test < t; ++test) {
  120.         read();
  121.         cout << total() << "\n";
  122.         if (total() < w) {
  123.             cout << "-1\n";
  124.             continue;
  125.         }
  126.         vector <long double> optimals(n);
  127.         for (int i = 0; i < n; ++i) {
  128.             optimals[i] = find_optimal(i);
  129.         }
  130.         int max_weight = 0;
  131.         for (int weight : weights) max_weight = max(max_weight, weight);
  132.         long double dp[n + 1][w + max_weight + 1];
  133.         for (int i = 0; i <= n; ++i) {
  134.             for (int j = 0; j <= w + max_weight; ++j) {
  135.                 dp[i][j] = 1e9;
  136.             }
  137.         }
  138.         dp[0][0] = 0;
  139.         for (int i = 1; i <= n; ++i) {
  140.             for (int j = 0; j <= w + max_weight; ++j) {
  141.                 dp[i][j] = dp[i - 1][j];
  142.             }
  143.             for (int j = 1; j <= w + max_weight; ++j) {
  144.                 if (j >= weights[i]) {
  145.                     if (dp[i - 1][j - weights[i - 1]] - 1e9 < EPS) {
  146.                         dp[i][j] = min(dp[i][j], dp[i - 1][j - weights[i - 1]] + optimals[i - 1]);
  147.                     }
  148.                 }
  149.             }
  150.         }
  151.         long double out = 1e9;
  152.         for (int i = w; i <= w + max_weight; ++i) {
  153.             out = min(out, dp[n][i]);
  154.         }
  155.         cout << out << "\n";
  156.     }
  157.     return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement