Advertisement
K_Y_M_bl_C

Untitled

Mar 26th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.84 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. };
  59.  
  60. ll dst(Point a, Point b)
  61. {
  62.     return sqr(a.x - b.x) + sqr(a.y - b.y);
  63. }
  64.  
  65. Point makeV(Point a, Point b)
  66. {
  67.     return b - a;
  68. }
  69.  
  70. struct event
  71. {
  72.     int x, l, r;
  73.     event() {};
  74.     event(int x, int l, int r) : x(x), l(l), r(r) {};
  75.     bool operator< (event &a) const
  76.     {
  77.         if (x == a.x)
  78.             return l < a.l;
  79.         return x < a.x;
  80.     }
  81. };
  82.  
  83. ll mysqrt(ll x)
  84. {
  85.     ll l = 0, r = 1e6;
  86.     while (r - l > 1)
  87.     {
  88.         ll mid = l + r >> 1;
  89.         if (mid * mid <= x)
  90.             l = mid;
  91.         else
  92.             r = mid;
  93.     }
  94.     return l;
  95. }
  96.  
  97. int solve()
  98. {
  99.     int n;
  100.     cin >> n;
  101.     vector<Point> a(n);
  102.     Point l, r;
  103.     for (int i = 0; i < n; ++i)
  104.     {
  105.         cin >> a[i].x >> a[i].y;
  106.         if (!i)
  107.         {
  108.             l = a[i], r = a[i];
  109.         }
  110.         else
  111.         {
  112.             if (a[i].x < l.x || a[i].x == l.x && a[i].y < l.y)
  113.                 l = a[i];
  114.             if (a[i].x > r.x || a[i].x == r.x && a[i].y < r.y)
  115.                 r = a[i];
  116.         }
  117.     }
  118.     vector<Point> up, dn;
  119.     up.inb(l);
  120.     dn.inb(l);
  121.     Point veclr = makeV(l, r);
  122.     for (int i = 0; i < n; ++i)
  123.     {
  124.         Point vec = makeV(l, a[i]);
  125.         ll crpr = vec * veclr;
  126.         if (crpr < 0)
  127.             up.inb(a[i]);
  128.         if (crpr > 0)
  129.             dn.inb(a[i]);
  130.     }
  131.     sort(up.begin() + 1, up.end(), [&](Point p, Point t)
  132.     {
  133.         Point v = makeV(up[0], p);
  134.         Point v1 = makeV(up[0], t);
  135.         return v * v1 < 0;
  136.     });
  137.     sort(dn.begin() + 1, dn.end(), [&](Point p, Point t)
  138.     {
  139.         Point v = makeV(dn[0], p);
  140.         Point v1 = makeV(dn[0], t);
  141.         return v * v1 > 0;
  142.     });
  143.     up.inb(r);
  144.     dn.inb(r);
  145.     int q;
  146.     cin >> q;
  147.     vector<event> sc;
  148.     while (q--)
  149.     {
  150.         ll x, y, R;
  151.         cin >> x >> y >> R;
  152.         for (int cx = max(l.x, x - R); cx <= min(r.x, x + R); ++cx)
  153.         {
  154.             ll val = mysqrt(R * R - (cx - x) * (cx - x));
  155.             sc.inb(event(cx, y - val, y + val));
  156.         }
  157.     }
  158.     sort(all(sc));
  159.     int iu = 1;
  160.     int id = 1;
  161.     int i = 0;
  162.     ll ans = 0;
  163.     while (i < (int)sc.size())
  164.     {
  165.         int cx = sc[i].x;
  166.         while (cx > up[iu].x)
  167.             ++iu;
  168.         while (cx > dn[id].x)
  169.             ++id;
  170.         vector<pii> s;
  171.         Point vup = makeV(up[iu - 1], up[iu]);
  172.         Point vdn = makeV(dn[id - 1], dn[id]);
  173.         ll U;
  174.         //up check
  175.         {
  176.             ll L = -2e9, R = 2e9;
  177.             while (R - L > 1)
  178.             {
  179.                 ll mid = (L + R) / 2ll;
  180.                 Point vcur = makeV(up[iu - 1], Point(cx, mid));
  181.                 if (vcur * vup < 0)
  182.                     R = mid;
  183.                 else
  184.                     L = mid;
  185.             }
  186.             U = L;
  187.         }
  188.         ll D;
  189.         //down check
  190.         {
  191.             ll L = -2e9, R = 2e9;
  192.             while (R - L > 1)
  193.             {
  194.                 ll mid = (L + R) / 2ll;
  195.                 Point vcur = makeV(dn[id - 1], Point(cx, mid));
  196.                 if (vcur * vdn <= 0)
  197.                     R = mid;
  198.                 else
  199.                     L = mid;
  200.             }
  201.             D = R;
  202.         }
  203.         while (i < (int)sc.size() && sc[i].x == cx)
  204.         {
  205.             ll cl = max((ll)sc[i].l, D);
  206.             ll cr = min((ll)sc[i].r, U);
  207.             if (cl <= cr)
  208.             {
  209.                 s.inb(mk(cl, -1));
  210.                 s.inb(mk(cr, 1));
  211.             }
  212.             ++i;
  213.         }
  214.         sort(all(s));
  215.         ll lst = -1;
  216.         int bal = 0;
  217.         for (auto &e : s)
  218.         {
  219.             bal += e.Y;
  220.             if (bal == -1 && e.Y == -1)
  221.                 lst = e.X;
  222.             if (bal == 0 && e.Y == 1)
  223.             {
  224.                 ans += e.X - lst + 1;
  225.             }
  226.         }
  227.     }
  228.     printf("%lld\n", ans);
  229.     return 0;
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement