Guest User

Untitled

a guest
Mar 28th, 2017
1,910
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <set>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const long long Q = -(1ll << 60);
  8. struct line {
  9.     long long m, p;
  10.     mutable set<line>::iterator prev;
  11. };
  12. set<line>::iterator null;
  13. bool operator<(const line& a, const line& b)
  14. {
  15.     if (b.p != Q && a.p != Q) {
  16.         return a.m < b.m;
  17.     }
  18.     if (b.p == Q) {
  19.         if (a.prev == null)
  20.             return true;
  21.         bool ok = true;
  22.         if ((a.prev->m - a.m) < 0)
  23.             ok = !ok;
  24.         if (ok) {
  25.             return (a.p - a.prev->p) < (a.prev->m - a.m) * b.m;
  26.         }
  27.         else {
  28.             return (a.p - a.prev->p) > (a.prev->m - a.m) * b.m;
  29.         }
  30.     }
  31.     else {
  32.         if (b.prev == null)
  33.             return false;
  34.         bool ok = true;
  35.         if ((b.prev->m - b.m) < 0)
  36.             ok = !ok;
  37.         if (ok) {
  38.             return !((b.p - b.prev->p) < a.m * (b.prev->m - b.m));
  39.         }
  40.         else {
  41.             return !((b.p - b.prev->p) > a.m * (b.prev->m - b.m));
  42.         }
  43.     }
  44. }
  45. class convex_hull {
  46. public:
  47.     set<line> convex;
  48.     set<line>::iterator next(set<line>::iterator ii)
  49.     {
  50.         set<line>::iterator gg = ii;
  51.         gg++;
  52.         return gg;
  53.     }
  54.     set<line>::iterator prev(set<line>::iterator ii)
  55.     {
  56.         set<line>::iterator gg = ii;
  57.         gg--;
  58.         return gg;
  59.     }
  60.     bool bad(set<line>::iterator jj)
  61.     {
  62.         set<line>::iterator ii, kk;
  63.         if (jj == convex.begin())
  64.             return false;
  65.         kk = next(jj);
  66.         if (kk == convex.end())
  67.             return false;
  68.         ii = prev(jj);
  69.         line a = *ii, c = *kk, b = *jj;
  70.         bool ok = true;
  71.         if ((b.m - a.m) < 0)
  72.             ok = !ok;
  73.         if ((b.m - c.m) < 0)
  74.             ok = !ok;
  75.         if (ok) {
  76.             return (c.p - b.p) * (b.m - a.m) <= (a.p - b.p) * (b.m - c.m);
  77.         }
  78.         else {
  79.             return (c.p - b.p) * (b.m - a.m) >= (a.p - b.p) * (b.m - c.m);
  80.         }
  81.     }
  82.     void del(set<line>::iterator ii)
  83.     {
  84.         set<line>::iterator jj = next(ii);
  85.         if (jj != convex.end()) {
  86.             jj->prev = ii->prev;
  87.         }
  88.         convex.erase(ii);
  89.     }
  90.     void add(long long m, long long p)
  91.     {
  92.         null = convex.end();
  93.         line g;
  94.         g.m = m;
  95.         g.p = p;
  96.         set<line>::iterator ii = convex.find(g);
  97.         if (ii != convex.end()) {
  98.             if (ii->p >= p)
  99.                 return;
  100.             del(ii);
  101.         }
  102.         convex.insert(g);
  103.         ii = convex.find(g);
  104.         set<line>::iterator jj = next(ii);
  105.         if (jj != convex.end())
  106.             jj->prev = ii;
  107.         if (ii != convex.begin()) {
  108.             ii->prev = prev(ii);
  109.         }
  110.         else {
  111.             ii->prev = convex.end();
  112.         }
  113.         if (bad(ii)) {
  114.             del(ii);
  115.             return;
  116.         }
  117.         jj = next(ii);
  118.         while (jj != convex.end() && bad(jj)) {
  119.             del(jj);
  120.             jj = next(ii);
  121.         }
  122.         if (ii != convex.begin()) {
  123.             jj = prev(ii);
  124.             while (ii != convex.begin() && bad(jj)) {
  125.                 del(jj);
  126.                 jj = prev(ii);
  127.             }
  128.         }
  129.     }
  130.     long long query(long long x)
  131.     {
  132.         null = convex.end();
  133.         line y;
  134.         y.m = x;
  135.         y.p = Q;
  136.         set<line>::iterator ii = convex.lower_bound(y);
  137.         ii--;
  138.         return ii->m * x + ii->p;
  139.     }
  140. };
  141.  
  142.  
  143. convex_hull gg;
  144. int main()
  145. {
  146.     gg.add(2,0);
  147.     gg.add(3,0);
  148.     cout<<gg.query(4)<<endl;
  149.     cout<<gg.query(-4)<<endl;
  150. }
RAW Paste Data