peltorator

Convex Hull Trick

Mar 6th, 2017
230
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. typedef long long integer;
  3. typedef long double ld;
  4.  
  5. struct Line
  6. {
  7.     integer k, b;
  8.     Line():
  9.         k(0),
  10.         b(0) {}
  11.     Line(integer k, integer b):
  12.         k(k),
  13.         b(b) {}
  14.  
  15.     ld operator()(ld x)
  16.     {
  17.         return x * (ld)k + (ld)b;
  18.     }
  19. };
  20.  
  21. const integer INF = 2e18; // change
  22.  
  23. struct CHT
  24. {
  25.     vector<Line> lines;
  26.     bool mini; // cht on minimum
  27.  
  28.     ld f(Line l1, Line l2)
  29.     {
  30.         return (ld)(l1.b - l2.b) / (ld)(l2.k - l1.k);
  31.     }
  32.  
  33.     void addLine(integer k, integer b)
  34.     {
  35.         if (!mini)
  36.         {
  37.             k = -k;
  38.             b = -b;
  39.         }
  40.         Line l(k, b);
  41.         while (lines.size() > 1)
  42.         {
  43.             if (lines.back().k == k)
  44.             {
  45.                 if (lines.back().b > b)
  46.                     lines.pop_back();
  47.                 else
  48.                     break;
  49.                 continue;
  50.             }
  51.             ld x1 = f(lines.back(), l);
  52.             ld x2 = f(lines.back(), lines[lines.size() - 2]);
  53.             if (x1 > x2)
  54.                 break;
  55.             lines.pop_back();
  56.         }
  57.         if (!lines.size() || lines.back().k != k)
  58.             lines.push_back(l);
  59.     }
  60.  
  61.     CHT(vector<pair<integer, integer> > v, bool ok = 1) // change
  62.     {
  63.         mini = ok;
  64.         lines.clear();
  65.         for (int i = 0; i < v.size(); i++)
  66.             addLine(v[i].first, v[i].second);
  67.     }
  68.  
  69.     integer getmin(integer x) //find of integer!
  70.     {
  71.         if (!lines.size())
  72.             return (mini ? INF : -INF);
  73.         int l = 0, r = lines.size();
  74.         while (r - l > 1)
  75.         {
  76.             int mid = (r + l) / 2;
  77.             if (f(lines[mid], lines[mid - 1]) <= (ld)x)
  78.                 l = mid;
  79.             else
  80.                 r = mid;
  81.         }
  82.         integer ans = lines[l].k * x + lines[l].b;
  83.         return (mini ? ans : -ans);
  84.     }
  85. };
RAW Paste Data