Advertisement
cosenza987

Untitled

Feb 10th, 2024
998
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.00 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. using ld = long double;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     cout << setprecision(15) << fixed;
  13.     ld x, y;
  14.     cin >> x >> y;
  15.     ld xi, yi;
  16.     cin >> xi >> yi;
  17.     ld vr, vs;
  18.     cin >> vr >> vs;
  19.     int n, s;
  20.     cin >> n >> s;
  21.     vector<pair<int, int>> v(n);
  22.     for(int i = 0; i < n; i++) {
  23.         cin >> v[i].first >> v[i].second;
  24.     }
  25.     vector<vector<ld>> f_tsp(n, vector<ld>(1 << n, numeric_limits<ld>::infinity())), dist(n, vector<ld>(n)), dp(n, vector<ld>(1 << n, numeric_limits<ld>::infinity()));
  26.     vector<ld> to_icecream(1 << n, numeric_limits<ld>::infinity()), b2b(1 << n, numeric_limits<ld>::infinity());
  27.     function<ld(ld, ld, ld, ld)> calc = [&](ld a, ld b, ld c, ld d) {
  28.         ld l = -1e6, r = 1e6;
  29.         for(int _ = 0; _ < 100; _++) {
  30.             ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
  31.             ld t1 = sqrtl((a - m1) * (a - m1) + b * b) / vr + sqrtl((c - m1) * (c - m1) + d * d) / vs;
  32.             ld t2 = sqrtl((a - m2) * (a - m2) + b * b) / vr + sqrtl((c - m2) * (c - m2) + d * d) / vs;
  33.             if(t1 > t2) {
  34.                 l = m1;
  35.             } else {
  36.                 r = m2;
  37.             }
  38.         }
  39.         return sqrtl((a - l) * (a - l) + b * b) / vr + sqrtl((c - l) * (c - l) + d * d) / vs;
  40.     };
  41.     for(int i = 0; i < n; i++) {
  42.         f_tsp[i][1 << i] = calc(x, y, v[i].first, v[i].second);
  43.         dp[i][1 << i] = calc(xi, yi, v[i].first, v[i].second);
  44.     }
  45.     function<ld(int, int)> calc2 = [&](int i, int j) {
  46.         ld l = 0, r = abs(v[i].first - v[j].first);
  47.         for(int _ = 0; _ < 100; _++) {
  48.             ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
  49.             ld t1 = hypotl(abs(v[i].first - v[j].first) - m1, v[i].second + v[j].second) / vs + m1 / vr;
  50.             ld t2 = hypotl(abs(v[i].first - v[j].first) - m2, v[i].second + v[j].second) / vs + m2 / vr;
  51.             if(t1 > t2) {
  52.                 l = m1;
  53.             } else {
  54.                 r = m2;
  55.             }
  56.         }
  57.         return hypotl(abs(v[i].first - v[j].first) - l, v[i].second + v[j].second) / vs + l / vr;
  58.     };
  59.     for(int i = 0; i < n; i++) {
  60.         for(int j = 0; j < n; j++) {
  61.             if(i == j) {
  62.                 dist[i][j] = 0;
  63.                 continue;
  64.             }
  65.             dist[i][j] = hypotl(v[i].first - v[j].first, v[i].second - v[j].second) / vs;
  66.             dist[i][j] = min(dist[i][j], calc2(i, j));
  67.         }
  68.     }
  69.     for(int msk = 1; msk < (1 << n); msk++) {
  70.         for(int j = 0; j < n; j++) {
  71.             for(int k = 0; k < n; k++) {
  72.                 if((msk >> j) & 1 and !((msk >> k) & 1)) {
  73.                     f_tsp[k][msk ^ (1 << k)] = min(f_tsp[k][msk ^ (1 << k)], f_tsp[j][msk] + dist[j][k]);
  74.                 }
  75.             }
  76.             if((msk >> j) & 1) {
  77.                 to_icecream[msk] = min(to_icecream[msk], f_tsp[j][msk] + calc(xi, yi, v[j].first, v[j].second));
  78.             }
  79.         }
  80.     }
  81.     for(int msk = 1; msk < (1 << n); msk++) {
  82.         for(int j = 0; j < n; j++) {
  83.             for(int k = 0; k < n; k++) {
  84.                 if((msk >> j) & 1 and !((msk >> k) & 1)) {
  85.                     dp[k][msk ^ (1 << k)] = min(dp[k][msk ^ (1 << k)], dp[j][msk] + dist[j][k]);
  86.                 }
  87.             }
  88.             if((msk >> j) & 1) {
  89.                 b2b[msk] = min(b2b[msk], dp[j][msk] + calc(xi, yi, v[j].first, v[j].second));
  90.             }
  91.         }
  92.     }
  93.     vector<ld> dp2(1 << n, numeric_limits<ld>::infinity());
  94.     dp2[0] = 0;
  95.     for(int msk = 1; msk < (1 << n); msk++) {
  96.         if(__builtin_popcount(msk) <= s) {
  97.             dp2[msk] = to_icecream[msk];
  98.         }
  99.         for(int sm = msk; sm; sm = (sm - 1) & msk) {
  100.             int falta = msk ^ sm;
  101.             if(__builtin_popcount(falta) <= s) {
  102.                 dp2[msk] = min(dp2[msk], dp2[sm] + b2b[falta]);
  103.             }
  104.         }
  105.     }
  106.     cout << dp2.back() << "\n";
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement