Advertisement
Tbl_Mne_Ne_Dryg

Untitled

Dec 22nd, 2022
549
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5. const int inf = 555;
  6. using ld = long double;
  7. const ld EPS = 0.000000001;
  8.  
  9. struct point {
  10.   ld x, y;
  11.   point() = default;
  12.   point(ld x, ld y) {
  13.     this->x = x;
  14.     this->y = y;
  15.   }
  16. };
  17.  
  18. bool operator == (point a, point b) {
  19.   return abs(a.x - b.x) < EPS && abs(a.y - b.y) < EPS;
  20. }
  21.  
  22. struct vect {
  23.   ld x, y;
  24. };
  25.  
  26. struct ship {
  27.   point x;
  28.   vect v;
  29. };
  30.  
  31. ld dist(point A, point B) {
  32.   return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
  33. }
  34.  
  35. struct circle {
  36.   point x;
  37.   bool can = true;
  38.   circle(point A, point B, point C) {
  39.     ld a = B.x - A.x;
  40.     ld b = B.y - A.y;
  41.     ld c = C.x - A.x;
  42.     ld d = C.y - A.y;
  43.     ld e = a * (A.x + B.x) + b * (A.y + B.y);
  44.     ld f = c * (A.x + C.x) + d * (A.y + C.y);
  45.     ld g = 2 * (a * (C.y - B.y) - b * (C.x - B.x));
  46.     if (abs(g) < EPS) {
  47.       can = false;
  48.       return;
  49.     }
  50.     x.x = (d * e - b * f) / g;
  51.     x.y = (a * f - c * e) / g;
  52.   }
  53. };
  54.  
  55. pair<int, point> f(vector<ship> sh, ld t, ld R) {
  56.   for (auto& i : sh) {
  57.     i.x.x += i.v.x * t;
  58.     i.x.y += i.v.y * t;
  59.   }
  60.   if (sh.size() == 1) {
  61.     return {1, sh[0].x};
  62.   }
  63.   if (sh.size() == 2) {
  64.     point c((sh[0].x.x + sh[1].x.x) / 2, (sh[0].x.y + sh[1].x.y) / 2);
  65.     if (dist(c, sh[0].x) > R) {
  66.       return {0, {}};
  67.     } else {
  68.       return {1, c};
  69.     }
  70.   }
  71.   point A = sh[0].x;
  72.   point B = sh[1].x;
  73.   for (int i = 0; i < sh.size(); i++)
  74.     for (int j = i + 1; j < sh.size(); j++)
  75.       if (dist(A, B) < dist(sh[i].x, sh[j].x)) {
  76.         A = sh[i].x;
  77.         B = sh[j].x;
  78.       }
  79.   for (auto& [C, v] : sh) {
  80.     if (C == A || C == B)
  81.       continue;
  82.     circle c(A, B, C);
  83.     if (!c.can) {
  84.       c.x = {(A.x + C.x) / 2, (A.y + C.y) / 2};
  85.     }
  86.     bool ch = true;
  87.     for (int i = 0; i < sh.size(); i++)
  88.       if (dist(sh[i].x, c.x) > R)
  89.         ch = false;
  90.     if (ch) {
  91.       return {true, c.x};
  92.     }
  93.   }
  94.   return {false, point()};
  95. }
  96.  
  97. tuple<bool, int, point> check(vector<ship>& sh, ld R) {
  98.   ld l = 0, r = 1e6, eps = 0.00000001;
  99.   while (l + eps < r) {
  100.     ld m1 = l + (r - l) / 3;
  101.     ld m2 = r - (r - l) / 3;
  102.     if (f(sh, m1, R).first > f(sh, m2, R).first)
  103.       l = m1;
  104.     else
  105.       r = m2;
  106.   }
  107.   for (int i = floor(l); i <= ceil(r); i++)
  108.     if (f(sh, i, R).first)
  109.       return make_tuple(1, i, f(sh, i, R).second);
  110.   return make_tuple(0, -1, point());
  111. }
  112.  
  113. signed main() {
  114.   ios::sync_with_stdio(false);
  115.   cin.tie(0);
  116. #ifdef LOCAL
  117.   freopen("input", "r", stdin);
  118. #endif
  119.   cout << fixed << setprecision(8);
  120.   int n, r;
  121.   cin >> n >> r;
  122.   vector<ship> sh(n);
  123.   for (int i = 0; i < n; i++) {
  124.     cin >> sh[i].x.x >> sh[i].x.y >>
  125.       sh[i].v.x >> sh[i].v.y;
  126.   }
  127.   vector<int> dp(1 << n, inf);
  128.   vector<int> pr(1 << n);
  129.   dp[0] = 0;
  130.   pr[0] = -1;
  131.   for (int mask = 1; mask < (1 << n); mask++) {
  132.     for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
  133.       int relax;
  134.       relax = dp[mask ^ sub] + 1;
  135.       vector<ship> a;
  136.       for (int i = 0; i < n; i++)
  137.         if ((sub >> i) & 1)
  138.           a.push_back(sh[i]);
  139.       if (get<0>(check(a, r)) && relax < dp[mask]) {
  140.         dp[mask] = relax;
  141.         pr[mask] = sub;
  142.       }
  143.     }
  144.   }
  145.   cout << dp[(1 << n) - 1] << '\n';
  146.   int mask = (1 << n) - 1;
  147.   while (mask != 0) {
  148.     vector<ship> cur;
  149.     for (int i = 0; i < n; i++)
  150.       if ((pr[mask] >> i) & 1)
  151.         cur.push_back(sh[i]);
  152.     auto ch = check(cur, r);
  153.     cout << get<1>(ch) << ' ' << get<2>(ch).x << ' ' << get<2>(ch).y << '\n';
  154.     mask ^= pr[mask];
  155.   }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement