fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <assert.h>
  4. #include <set>
  5. #include <map>
  6. #include <complex>
  7. #include <iostream>
  8. #include <time.h>
  9. #include <stack>
  10. #include <stdlib.h>
  11. #include <memory.h>
  12. #include <bitset>
  13. #include <math.h>
  14. #include <string>
  15. #include <string.h>
  16. #include <queue>
  17. #include <vector>
  18.  
  19. using namespace std;
  20.  
  21. const int MaxN = 1e5 + 10;
  22. const int MOD = 1e9 + 7;
  23. const int INF = 1e9;
  24.  
  25. typedef long double PrecisionType;
  26. typedef pair < PrecisionType, PrecisionType > PointType;
  27.  
  28. const PrecisionType EPS = 1e-10;
  29.  
  30. struct Node {
  31.   PointType x;
  32.   int y, sz;
  33.   PrecisionType sq;
  34.   PointType lmost, rmost;
  35.   Node *l, *r;
  36.   Node() {
  37.   }
  38.   Node(PointType _x) : sq(0.0), x(_x), lmost(_x), rmost(_x), sz(1), y(rand() * RAND_MAX + rand()), l(NULL), r(NULL) {
  39.   }
  40.   friend int getSize(Node *t) {
  41.     return t != NULL ? t->sz : 0;
  42.   }
  43.   friend PrecisionType getSquare(Node *t) {
  44.     return t ? t->sq : 0;
  45.   }
  46.   friend void update(Node *t) {
  47.     if (t != NULL) {
  48.       t->sz = 1;
  49.       t->lmost = t->rmost = t->x;
  50.       t->sq = 0;
  51.       if (t->r != NULL) {
  52.         t->sq += t->r->sq;
  53.         t->sq += (PrecisionType)(+t->r->lmost.first - t->x.first) * (PrecisionType)(t->r->lmost.second + t->x.second);
  54.         t->rmost = t->r->rmost;
  55.         t->sz += t->r->sz;
  56.       }
  57.       if (t->l != NULL) {
  58.         t->sq += t->l->sq;
  59.         t->sq += (PrecisionType)(-t->l->rmost.first + t->x.first) * (PrecisionType)(t->l->rmost.second + t->x.second);
  60.         t->lmost = t->l->lmost;
  61.         t->sz += t->l->sz;
  62.       }
  63.     }
  64.   }
  65.   friend void split(Node *t, Node *&l, Node *&r, PointType x) {
  66.     if (!t) {
  67.       r = l = NULL;
  68.       return;
  69.     }
  70.     if (t->x.first <= x.first) {
  71.       split(t->r, t->r, r, x);
  72.       l = t;
  73.       update(l);
  74.       return;
  75.     }
  76.     split(t->l, l, t->l, x);
  77.     r = t;
  78.     update(r);
  79.   }
  80.   friend Node* merge(Node *l, Node *r) {
  81.     if (!l || !r) {
  82.       return l ? l : r;
  83.     }
  84.     if (l->y > r->y) {
  85.       l->r = merge(l->r, r);
  86.       update(l);
  87.       return l;
  88.     }
  89.     r->l = merge(l, r->l);
  90.     update(r);
  91.     return r;
  92.   }
  93. };
  94.  
  95. PrecisionType dist(PointType a, PointType b) {
  96.   return hypotl(a.first - b.first + .0, a.second - b.second + .0);
  97. }
  98.  
  99. PrecisionType dist2(PointType a, PointType b) {
  100.   return (b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second);
  101. }
  102.  
  103. PrecisionType cw(PointType a, PointType b, PointType c) {
  104.   return (a.first - b.first) * (c.second - b.second) - (a.second - b.second) * (c.first - b.first);
  105. }
  106.  
  107. bool upcw(PointType a, PointType b, PointType c) {
  108.   return cw(a, b, c) > 0;
  109. }
  110.  
  111. bool dwcw(PointType a, PointType b, PointType c) {
  112.   return cw(a, b, c) < 0;
  113. }
  114.  
  115. PrecisionType getY(PointType a, PointType b, PointType c) {
  116.   return (c.first - a.first) / (b.first - a.first) * (b.second - a.second) + a.second;
  117. }
  118.  
  119. Node *leftFound(Node *root, PointType point, bool (*myCw)(PointType, PointType, PointType)) {
  120.   if (root->l != NULL) {
  121.     if (!myCw(root->l->rmost, root->x, point)) {
  122.       return leftFound(root->l, point, myCw);
  123.     }
  124.   }
  125.   if (root->r != NULL) {
  126.     if (myCw(root->x, root->r->lmost, point)) {
  127.       return leftFound(root->r, point, myCw);
  128.     }
  129.   }
  130.   return root;
  131. }
  132.  
  133. Node *rightFound(Node *root, PointType point, bool (*myCw)(PointType, PointType, PointType)) {
  134.   if (root->r != NULL) {
  135.     if (!myCw(point, root->x, root->r->lmost)) {
  136.       return rightFound(root->r, point, myCw);
  137.     }
  138.   }
  139.   if (root->l != NULL) {
  140.     if (myCw(point, root->l->rmost, root->x)) {
  141.       return rightFound(root->l, point, myCw);
  142.     }
  143.   }
  144.   return root;
  145. }
  146.  
  147. bool exist(Node *root, PointType p) {
  148.   if (!root) {
  149.     return false;
  150.   }
  151.   if (root->x.first == p.first) {
  152.     return true;
  153.   }
  154.   if (root->x.first < p.first) {
  155.     return exist(root->r, p);
  156.   }
  157.   return exist(root->l, p);
  158. }
  159.  
  160. bool addPoint(vector < pair < PointType, Node* > > &roll, Node *&convexHull, PointType point, bool isUp, bool (*myCw)(PointType, PointType, PointType)) {
  161.   if (exist(convexHull, point)) {
  162.     return false;
  163.   }
  164.   if (!convexHull) {
  165.     convexHull = new Node(point);
  166.     roll.push_back(make_pair(point, (Node*)NULL));
  167.     return true;
  168.   }
  169.   if (convexHull->lmost <= point && point <= convexHull->rmost) {
  170.     Node *leftConvexHull, *rightConvexHull;
  171.     split(convexHull, leftConvexHull, rightConvexHull, point);
  172.     PointType l = leftConvexHull->rmost;
  173.     PointType r = rightConvexHull->lmost;
  174.     PrecisionType y = getY(l, r, point);
  175.     if (isUp == true && point.second > y || isUp == false && point.second < y) {
  176.       Node *whereL = leftFound(leftConvexHull, point, myCw);
  177.       Node *whereR = rightFound(rightConvexHull, point, myCw);
  178.       Node *a, *b;
  179.       split(leftConvexHull, leftConvexHull, a,  make_pair(whereL->x.first, whereL->x.second));
  180.       split(rightConvexHull, b, rightConvexHull, make_pair(whereR->x.first - 1e-10, whereR->x.second));
  181.       convexHull = merge(leftConvexHull, merge(new Node(point), rightConvexHull));
  182.       roll.push_back(make_pair(point, merge(a, b)));
  183.       return true;
  184.     }
  185.     convexHull = merge(leftConvexHull, rightConvexHull);
  186.     return false;
  187.   }
  188.   if (point <= convexHull->lmost) {
  189.     Node *whereR = rightFound(convexHull, point, myCw);
  190.     Node *temp;
  191.     split(convexHull, temp, convexHull, make_pair(whereR->x.first - 1e-10, whereR->x.second));
  192.     roll.push_back(make_pair(point, temp));
  193.     convexHull = merge(new Node(point), convexHull);
  194.   } else {
  195.     Node *whereL = leftFound(convexHull, point, myCw);
  196.     Node *temp;
  197.     split(convexHull, convexHull, temp, make_pair(whereL->x.first, whereL->x.second));
  198.     roll.push_back(make_pair(point, temp));
  199.     convexHull = merge(convexHull, new Node(point));
  200.   }
  201.   return true;
  202. }
  203.  
  204. PointType rotate(PointType point, PrecisionType ang) {
  205.   return PointType(point.first * cosl(ang) + point.second * sinl(ang), -point.first * sinl(ang) + point.second * cosl(ang));
  206. }
  207.  
  208. void makeChange(Node *&upConvexHull,
  209.            Node *&downConvexHull,
  210.            vector < pair < PointType, Node* > > &upChanges,
  211.            vector < pair < PointType, Node* > > &downChanges,
  212.            PointType point) {
  213.   addPoint(upChanges, upConvexHull, point, true, upcw);
  214.   addPoint(downChanges, downConvexHull, point, false, dwcw);
  215. }
  216.  
  217. void rollback(Node *&convexHull, vector < pair < PointType, Node* > > &roll, int oldSize) {
  218.   while (roll.size() > oldSize) {
  219.     PointType cur = roll.back().first;
  220.     Node *tree = roll.back().second;
  221.     Node *a, *b;
  222.     split(convexHull, convexHull, a, make_pair(cur.first - 1e-10, cur.second));
  223.     split(a, a, b, make_pair(cur.first + 1e-10, cur.second));
  224.     convexHull = merge(convexHull, merge(tree, b));
  225.     roll.pop_back();
  226.   }
  227. }
  228.  
  229. void solve(Node *&upConvexHull,
  230.            Node *&downConvexHull,
  231.            vector < pair < PointType, Node* > > &upChanges,
  232.            vector < pair < PointType, Node* > > &downChanges,
  233.            vector < pair < char, PointType > > &queries,
  234.            vector < int > &wadd,
  235.            vector < int > &paired,
  236.            vector < PrecisionType > &answers,
  237.            int lbound, int rbound) {
  238.   int middle = (lbound + rbound) / 2;
  239.   int upch = upChanges.size(), dwch = downChanges.size();
  240.   vector < int > nadd;
  241.   for (int i = 0; i < (int)wadd.size(); ++i) {
  242.     int l = wadd[i], r = paired[l];
  243.     if (r < lbound || l > rbound) {
  244.       continue;
  245.     }
  246.     if (l <= lbound && r > rbound) {
  247.       makeChange(upConvexHull, downConvexHull, upChanges, downChanges, queries[l].second);
  248.       continue;
  249.     }
  250.     nadd.push_back(wadd[i]);
  251.   }
  252.   if (lbound != rbound) {
  253.     solve(upConvexHull, downConvexHull, upChanges, downChanges, queries, nadd, paired, answers, lbound, middle);
  254.     solve(upConvexHull, downConvexHull, upChanges, downChanges, queries, nadd, paired, answers, middle + 1, rbound);
  255.   } else {
  256.     answers[lbound] = abs((getSquare(upConvexHull) - getSquare(downConvexHull)) / 2.0);
  257.   }
  258.   rollback(upConvexHull, upChanges, upch);
  259.   rollback(downConvexHull, downChanges, dwch);
  260. }
  261.  
  262. vector < PrecisionType > solveSmart(vector < pair < char, PointType > > queries) {
  263.   int q = (int)queries.size();
  264.   map < PointType, vector < int > > f;
  265.   vector < int > paired(q);
  266.   for (int i = 0; i < q; ++i) {
  267.     char type = queries[i].first;
  268.     PointType point = queries[i].second;
  269.     if (type == '+') {
  270.       f[point].push_back(i);
  271.     } else {
  272.       int where = f[point].back();
  273.       f[point].pop_back();
  274.       paired[where] = i;
  275.       paired[i] = where;
  276.     }
  277.   }
  278.   vector < int > wadd;
  279.   for (int i = 0; i < q; ++i) {
  280.     char type = queries[i].first;
  281.     PointType point = queries[i].second;
  282.     if (type == '+') {
  283.       wadd.push_back(i);
  284.     }
  285.     if (type == '-' || f[point].empty()) {
  286.       continue;
  287.     }
  288.     for (int j = 0; j < (int)f[point].size(); ++j) {
  289.       int where = f[point][j];
  290.       paired[where] = q;
  291.     }
  292.     f[point].clear();
  293.   }
  294.   vector < PrecisionType > ans(q);
  295.   Node *upConvexHull = NULL, *downConvexHull = NULL;
  296.   vector < pair < PointType, Node* > > upChanges, downChanges;
  297.   solve(upConvexHull, downConvexHull, upChanges, downChanges, queries, wadd, paired, ans, 0, q - 1);
  298.   return ans;
  299. }
  300.  
  301. namespace stupid {
  302.   vector < PointType > convexHull(vector < PointType > points) {
  303.     sort(points.begin(), points.end());
  304.     if (points.size() < 3) {
  305.       return points;
  306.     }
  307.     vector < PointType > up, down;
  308.     up.push_back(points[0]);
  309.     down.push_back(points[0]);
  310.     for (int i = 1; i < (int)points.size(); ++i) {
  311.       if (i == (int)points.size() - 1 || cw(points[0], points[i], points.back()) > 0) {
  312.         while (up.size() >= 2 && cw(up[up.size() - 2], up[up.size() - 1], points[i]) <= 0) {
  313.           up.pop_back();
  314.         }
  315.         up.push_back(points[i]);
  316.       }
  317.       if (i == (int)points.size() - 1 || cw(points[0], points[i], points.back()) < 0) {
  318.         while (down.size() >= 2 && cw(down[down.size() - 2], down[down.size() - 1], points[i]) >= 0) {
  319.           down.pop_back();
  320.         }
  321.         down.push_back(points[i]);
  322.       }
  323.     }
  324.     vector < PointType > res;
  325.     for (int i = 0; i < (int)up.size(); ++i) {
  326.       res.push_back(up[i]);
  327.     }
  328.     for (int i = (int)down.size() - 2; i > 0; --i) {
  329.       res.push_back(down[i]);
  330.     }
  331.     return res;
  332.   }
  333.  
  334.   void solve(vector < pair < char, PointType > > queries) {
  335.     multiset < PointType > points;
  336.     for (int i = 0; i < (int)queries.size(); ++i) {
  337.       PointType point = queries[i].second;
  338.       if (queries[i].first == '+') {
  339.         points.insert(point);
  340.       } else {
  341.         if (points.find(point) != points.end()) {
  342.           points.erase(points.find(point));
  343.         }
  344.       }
  345.       PrecisionType ans = 0;
  346.       if (points.size() >= 3) {
  347.         vector < PointType > v(points.begin(), points.end());
  348.         v = convexHull(v);
  349.         if (v.size() >= 3) {
  350.           for (int i = 0; i < (int)v.size(); ++i) {
  351.             ans += (PrecisionType)(v[i].first - v[(i + 1) % v.size()].first) * (v[i].second + v[(i + 1) % v.size()].second);
  352.           }
  353.         }
  354.       }
  355.       long long res = (ans >= 0 ? (long long)(ans + 0.5) : (long long)(ans - 0.5));
  356.       printf("%lld.%lld\n", abs(res) / 2, abs(res) % 2 * 5);
  357.     }
  358.   }
  359. };
  360.  
  361. int main() {
  362.  // freopen("input.txt", "r", stdin);
  363.  // freopen("output.txt", "w", stdout);
  364.   int t;
  365.   scanf("%d", &t);
  366.   while (t --> 0) {
  367.     int q;
  368.     scanf("%d", &q);
  369.     vector < pair < char, PointType > > queries(q);
  370.     for (int i = 0; i < q; ++i) {
  371.       int x, y;
  372.       scanf("\n%c%d%d", &queries[i].first, &x, &y);
  373.       queries[i].second.first = x;
  374.       queries[i].second.second = y;
  375.     }
  376. //    stupid::solve(queries);
  377. //    exit(0);
  378.     for (int i = 0; i < q; ++i) {
  379.       queries[i].second = rotate(queries[i].second, +13.0);
  380.     }
  381.     vector < PrecisionType > ans = solveSmart(queries);
  382.     for (int i = 0; i < (int)ans.size(); ++i) {
  383.       printf("%.1lf\n", (double)ans[i]);
  384.     }
  385.   }
  386.   return 0;
  387. }
  388.  
Success #stdin #stdout 0s 3516KB
comments (?)
stdin
copy 
1
6
+ 0 0
+ 0 4
+ 4 0
+ 2 2
+ 4 4
- 0 0
stdout
copy 
0.0
0.0
8.0
8.0
16.0
8.0
https://ideone.com/HFUPg9
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!