Advertisement
K_Y_M_bl_C

Untitled

Mar 27th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.07 KB | None | 0 0
  1. #ifdef _DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <bits/stdc++.h>
  7.        
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10.            
  11. typedef long long ll;
  12. typedef vector<ll> vll;
  13. typedef pair<int, int> pii;
  14. typedef vector<int> vi;
  15. typedef long double ld;
  16. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  17.            
  18. #define mk make_pair
  19. #define inb push_back
  20. #define enb emplace_back
  21. #define X first
  22. #define Y second
  23. #define all(v) v.begin(), v.end()
  24. #define sqr(x) (x) * (x)
  25. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  26. #define y1 AYDARBOG
  27. //continue break pop_back return
  28.            
  29. int solve();
  30.            
  31. int main()
  32. {
  33.     //ios_base::sync_with_stdio(0);
  34.     //cin.tie(0);
  35. #define TASK "robots"
  36. #ifndef _DEBUG
  37.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  38. #endif
  39.     solve();
  40. #ifdef _DEBUG
  41.     fprintf(stderr, "\nTIME: %.3f\n", TIME);
  42. #endif
  43. }
  44.  
  45. struct Point
  46. {
  47.     ll x, y;
  48.     Point() {};
  49.     Point(ll x, ll y) : x(x), y(y) {};
  50.     Point operator-(Point a)
  51.     {
  52.         return Point(x - a.x, y - a.y);
  53.     }
  54.     ll operator*(Point a)
  55.     {
  56.         return x * a.y - y * a.x;
  57.     }
  58.     bool operator==(Point a)
  59.     {
  60.         return x == a.x && y == a.y;
  61.     }
  62. };
  63.  
  64. ll dst(Point a, Point b)
  65. {
  66.     return sqr(a.x - b.x) + sqr(a.y - b.y);
  67. }
  68.  
  69. Point makeV(Point a, Point b)
  70. {
  71.     return b - a;
  72. }
  73.  
  74. struct event
  75. {
  76.     int x, l, r;
  77.     event() {};
  78.     event(int x, int l, int r) : x(x), l(l), r(r) {};
  79.     bool operator< (event &a) const
  80.     {
  81.         if (x == a.x)
  82.             return l < a.l;
  83.         return x < a.x;
  84.     }
  85. };
  86.  
  87. ll mysqrt(ll x)
  88. {
  89.     ll l = 0, r = 3e9;
  90.     while (r - l > 1)
  91.     {
  92.         ll mid = l + r >> 1ll;
  93.         if (mid * mid <= x)
  94.             l = mid;
  95.         else
  96.             r = mid;
  97.     }
  98.     return l;
  99. }
  100.  
  101. int solve()
  102. {
  103.     int n;
  104.     cin >> n;
  105.     vector<Point> a(n);
  106.     Point l, r;
  107.     for (int i = 0; i < n; ++i)
  108.     {
  109.         cin >> a[i].x >> a[i].y;
  110.         if (!i)
  111.         {
  112.             l = a[i], r = a[i];
  113.         }
  114.         else
  115.         {
  116.             if (a[i].x < l.x || a[i].x == l.x && a[i].y < l.y)
  117.                 l = a[i];
  118.             if (a[i].x > r.x || a[i].x == r.x && a[i].y < r.y)
  119.                 r = a[i];
  120.         }
  121.     }
  122.     vector<Point> up, dn;
  123.     up.inb(l);
  124.     dn.inb(l);
  125.     Point veclr = makeV(l, r);
  126.     for (int i = 0; i < n; ++i)
  127.     {
  128.         Point vec = makeV(l, a[i]);
  129.         ll crpr = vec * veclr;
  130.         if (crpr < 0)
  131.             up.inb(a[i]);
  132.         if (crpr > 0)
  133.             dn.inb(a[i]);
  134.     }
  135.     up.inb(r);
  136.     dn.inb(r);
  137.     sort(up.begin() + 1, up.end(), [&](Point p, Point t)
  138.     {
  139.         Point v = makeV(up[0], p);
  140.         Point v1 = makeV(up[0], t);
  141.         return v * v1 < 0;
  142.     });
  143.     sort(dn.begin() + 1, dn.end(), [&](Point p, Point t)
  144.     {
  145.         Point v = makeV(dn[0], p);
  146.         Point v1 = makeV(dn[0], t);
  147.         return v * v1 > 0;
  148.     });
  149.     int q;
  150.     cin >> q;
  151.     vector<event> sc;
  152.     while (q--)
  153.     {
  154.         ll x, y, R;
  155.         cin >> x >> y >> R;
  156.         for (int cx = max(l.x, x - R); cx <= min(r.x, x + R); ++cx)
  157.         {
  158.             ll val = 0;
  159.             ll xx = cx - x;
  160.             {
  161.                 ll l = 0, r = 1e9;
  162.                 while (r - l > 1)
  163.                 {
  164.                     ll mid = l + r >> 1;
  165.                     if (sqr(xx) + sqr(mid) <= sqr(R))
  166.                         l = mid;
  167.                     else
  168.                         r = mid;
  169.                 }
  170.                 val = l;
  171.             }
  172.             sc.inb(event(cx, y - val, y + val));
  173.         }
  174.     }
  175.     sort(all(sc));
  176.     int iu = 1;
  177.     int id = 1;
  178.     int i = 0;
  179.     ll ans = 0;
  180.     while (i < (int)sc.size())
  181.     {
  182.         int cx = sc[i].x;
  183.         while (cx > up[iu].x)
  184.             ++iu;
  185.         while (cx > dn[id].x)
  186.             ++id;
  187.         vector<pii> s;
  188.         Point vup = makeV(up[iu - 1], up[iu]);
  189.         Point vdn = makeV(dn[id - 1], dn[id]);
  190.         ll U;
  191.         //up check
  192.         {
  193.             ll L = -2e9, R = 2e9;
  194.             while (R - L > 1)
  195.             {
  196.                 ll mid = (L + R) / 2ll;
  197.                 Point vcur = makeV(up[iu - 1], Point(cx, mid));
  198.                 if (vcur * vup < 0)
  199.                     R = mid;
  200.                 else
  201.                     L = mid;
  202.             }
  203.             U = L;
  204.         }
  205.         ll D;
  206.         //down check
  207.         {
  208.             ll L = -2e9, R = 2e9;
  209.             while (R - L > 1)
  210.             {
  211.                 ll mid = (L + R) / 2ll;
  212.                 Point vcur = makeV(dn[id - 1], Point(cx, mid));
  213.                 if (vcur * vdn <= 0)
  214.                     R = mid;
  215.                 else
  216.                     L = mid;
  217.             }
  218.             D = R;
  219.         }
  220.         while (i < (int)sc.size() && sc[i].x == cx)
  221.         {
  222.             ll cl = max((ll)sc[i].l, D);
  223.             ll cr = min((ll)sc[i].r, U);
  224.             if (cl <= cr)
  225.             {
  226.                 s.inb(mk(cl, -1));
  227.                 s.inb(mk(cr, 1));
  228.             }
  229.             ++i;
  230.         }
  231.         sort(all(s));
  232.         ll lst = -1;
  233.         int bal = 0;
  234.         for (auto &e : s)
  235.         {
  236.             bal += e.Y;
  237.             if (bal == -1 && e.Y == -1)
  238.                 lst = e.X;
  239.             if (bal == 0 && e.Y == 1)
  240.             {
  241.                 ans += e.X - lst + 1;
  242.             }
  243.         }
  244.     }
  245.     printf("%lld\n", ans);
  246.     return 0;
  247. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement