API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 27th, 2015
353
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.30 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <bitset>
  6. #include <deque>
  7. #include <queue>
  8. #include <string>
  9. #include <algorithm>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <ctime>
  14. #include <cmath>
  15. #include <cassert>
  16. #include <complex>
  17.  
  18. #define pb push_back
  19. #define pbk pop_back
  20. #define sz(a) ((int) (a).size())
  21. #define all(a) (a).begin(), (a).end()
  22. #define mp make_pair
  23. #define fs first
  24. #define sc second
  25. #define next _next
  26. #define prev _prev
  27. #define link _link
  28. #define hash _hash
  29.  
  30. #ifdef LOCAL42
  31. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  32. #else
  33. #define eprintf(...) 42
  34. #endif
  35.  
  36. #if _WIN32 || __WIN32__ || _WIN64 || __WIN64__
  37. #define LLD "%I64d"
  38. #else
  39. #define LLD "%lld"
  40. #endif
  41.  
  42. using namespace std;
  43.  
  44. typedef long long ll;
  45. typedef unsigned int uint;
  46. typedef unsigned long long ull;
  47. typedef long double ld;
  48. typedef vector<int> vi;
  49. typedef pair<int, int> pii;
  50.  
  51. const int inf = 1e9;
  52. const double eps = 1e-9;
  53. const double pi = 4 * atan(1.0);
  54. const int N = int(2e5) + 100;
  55. const int SIZE = int(1e6) + 100;
  56.  
  57. struct point {
  58.    
  59.     int x, y;
  60.    
  61.     point() {}
  62.    
  63.     point(int x, int y) : x(x), y(y) {}
  64.    
  65. };
  66.  
  67. point operator - (const point& a, const point& b) {
  68.     return point(a.x - b.x, a.y - b.y);
  69. }
  70.  
  71. point operator + (const point& a, const point& b) {
  72.     return point(a.x + b.x, a.y + b.y);
  73. }
  74.  
  75. inline ll vec(const point& a, const point& b) {
  76.     return 1LL * a.x * b.y - 1LL * b.x * a.y;
  77. }
  78.  
  79. inline int half(const point& p) {
  80.     if (p.x > 0 || (p.x == 0 && p.y > 0)) {
  81.         return 0;
  82.     }
  83.     return 1;
  84. }
  85.  
  86. bool operator < (const point& a, const point& b) {
  87.     int ha = half(a), hb = half(b);
  88.     if (ha != hb) {
  89.         return ha < hb;
  90.     }
  91.     ll v = vec(a, b);
  92.     if (v != 0) {
  93.         return v > 0;
  94.     }
  95.     return mp(a.x, a.y) < mp(b.x, b.y);
  96. }
  97.  
  98. bool operator == (const point& a, const point& b) {
  99.     return a.x == b.x && a.y == b.y;
  100. }
  101.  
  102. const int QUERY = 0;
  103. const int DEL = 1;
  104. const int ADD = 2;
  105.  
  106. struct event {
  107.    
  108.     int x, t, num, bal;
  109.    
  110.     event() {}
  111.    
  112.     event(int x, int t, int num, int bal) : x(x), t(t), num(num), bal(bal) {}
  113.    
  114. };
  115.  
  116. bool operator < (const event& a, const event& b) {
  117.     if (a.x != b.x) {
  118.         return a.x < b.x;
  119.     }
  120.     return a.t < b.t;
  121. }
  122.  
  123. struct node {
  124.    
  125.     int num, bal, sum_bal, h, p, l, r;
  126.    
  127. };
  128.  
  129. int n, m, k, cur = 0;
  130. point p[N], q[N];
  131. bool used[N], is_bridge[N];
  132. int u[N], v[N], tin[N], tout[N];
  133. set<pii> edges;
  134. vector<pii> lst;
  135. map<pii, int> num;
  136. set<int> xs;
  137. vector<pii> neig[N];
  138. bool ans[N];
  139. vector<pair<point, int> > g[N];
  140. vector<pair<point, point> > segs;
  141. vector<event> events;
  142. node d[SIZE];
  143. int node_num[SIZE];
  144.  
  145. inline int get_rand(int l, int r) {
  146.     return l + rand() % (r - l + 1);
  147. }
  148.  
  149. inline void rotate() {
  150.     for (;;) {
  151.         //cerr << "IT" << endl;
  152.         int a = get_rand(-1000, 1000), b = get_rand(-1000, 1000);
  153.         int c = get_rand(-1000, 1000), d = get_rand(-1000, 1000);
  154.         //int a = 4243, b = 1279;
  155.         //int c = -3516, d = 5757;
  156.         if (a * d - b * c == 0) {
  157.             //assert(false);
  158.             continue;
  159.         }
  160.         xs.clear();
  161.         bool good = true;
  162.         for (int i = 0; i < m; ++i) {
  163.             int x1 = a * p[u[i]].x + b * p[u[i]].y;
  164.             int x2 = a * p[v[i]].x + b * p[v[i]].y;
  165.             if (x1 == x2) {
  166.                 good = false;
  167.                 break;
  168.             }
  169.             xs.insert(x1);
  170.             xs.insert(x2);
  171.         }
  172.         if (!good) {
  173.             //assert(false);
  174.             continue;
  175.         }
  176.         /*for (int i = 0; i < k; ++i) {
  177.             int x = a * q[i].x + b * q[i].y;
  178.             if (xs.find(x) != xs.end()) {
  179.                 good = false;
  180.                 break;
  181.             }
  182.         }*/
  183.         if (good) {
  184.             for (int i = 0; i < n; ++i) {
  185.                 int x = a * p[i].x + b * p[i].y;
  186.                 int y = c * p[i].x + d * p[i].y;
  187.                 p[i].x = x;
  188.                 p[i].y = y;
  189.             }
  190.             for (int i = 0; i < k; ++i) {
  191.                 int x = a * q[i].x + b * q[i].y;
  192.                 int y = c * q[i].x + d * q[i].y;
  193.                 q[i].x = x;
  194.                 q[i].y = y;
  195.             }
  196.             break;
  197.         }
  198.         //assert(false);
  199.     }
  200. }
  201.  
  202. void dfs(int v, int pe = -1) {
  203.     used[v] = true;
  204.     tin[v] = tout[v] = cur++;
  205.     for (int i = 0; i < sz(neig[v]); ++i) {
  206.         if (neig[v][i].sc == pe) {
  207.             continue;
  208.         }
  209.         if (!used[neig[v][i].fs]) {
  210.             dfs(neig[v][i].fs, neig[v][i].sc);
  211.             tout[v] = min(tout[v], tout[neig[v][i].fs]);
  212.             if (tout[neig[v][i].fs] > tin[v]) {
  213.                 is_bridge[neig[v][i].sc] = true;
  214.             }
  215.         } else {
  216.             tout[v] = min(tout[v], tin[neig[v][i].fs]);
  217.         }
  218.     }
  219. }
  220.  
  221. inline void del_bridge() {
  222.     for (int i = 0; i < m; ++i) {
  223.         neig[u[i]].pb(mp(v[i], i));
  224.         neig[v[i]].pb(mp(u[i], i));
  225.     }
  226.     for (int i = 0; i < n; ++i) {
  227.         if (!used[i]) {
  228.             dfs(i);
  229.         }
  230.     }
  231.     int nm = 0;
  232.     for (int i = 0; i < m; ++i) {
  233.         if (!is_bridge[i]) {
  234.             u[nm] = u[i];
  235.             v[nm++] = v[i];
  236.         }
  237.     }
  238.     m = nm;
  239. }
  240.  
  241. inline void calc(int v) {
  242.     if (v == 0) {
  243.         return;
  244.     }
  245.     d[v].p = 0;
  246.     d[v].sum_bal = d[d[v].l].sum_bal + d[d[v].r].sum_bal + d[v].bal;
  247.     if (d[v].l) {
  248.         d[d[v].l].p = v;
  249.     }
  250.     if (d[v].r) {
  251.         d[d[v].r].p = v;
  252.     }
  253. }
  254.  
  255. inline double get_y(const pair<point, point>& s, int x) {
  256.     return s.fs.y + 1.0 * (s.sc.y - s.fs.y) * (x - s.fs.x) / (s.sc.x - s.fs.x);
  257. }
  258.  
  259. inline bool cmp(int a, int b, int x) {
  260.     if (x == segs[a].fs.x && x == segs[b].fs.x && segs[a].fs.y == segs[b].fs.y) {
  261.         return vec(segs[a].sc - segs[a].fs, segs[b].sc - segs[a].fs) > 0;
  262.     }
  263.     if (x == segs[a].sc.x && x == segs[b].sc.x && segs[a].sc.y == segs[b].sc.y) {
  264.         return vec(segs[a].sc - segs[a].fs, segs[b].sc - segs[a].fs) < 0;
  265.     }
  266.     return get_y(segs[a], x) < get_y(segs[b], x);
  267. }
  268.  
  269. void split(int v, int num, int x, int &l, int &r) {
  270.     if (v == 0) {
  271.         l = r = 0;
  272.         return;
  273.     }
  274.     if (cmp(d[v].num, num, x)) {
  275.         split(d[v].r, num, x, d[v].r, r);
  276.         l = v;
  277.     } else {
  278.         split(d[v].l, num, x, l, d[v].l);
  279.         r = v;
  280.     }
  281.     calc(v);
  282. }
  283.  
  284. int merge(int l, int r) {
  285.     if (l == 0) {
  286.         calc(r);
  287.         return r;
  288.     }
  289.     if (r == 0) {
  290.         calc(l);
  291.         return l;
  292.     }
  293.     int res;
  294.     if (d[l].h > d[r].h) {
  295.         d[l].r = merge(d[l].r, r);
  296.         res = l;
  297.     } else {
  298.         d[r].l = merge(l, d[r].l);
  299.         res = r;
  300.     }
  301.     calc(res);
  302.     return res;
  303. }
  304.  
  305. inline node new_node(int num, int bal) {
  306.     node res;
  307.     res.num = num;
  308.     res.bal = res.sum_bal = bal;
  309.     res.p = res.l = res.r = 0;
  310.     res.h = rand();
  311.     return res;
  312. }
  313.  
  314. inline void gen() {
  315.     int n = int(1e5), m = int(1e5), q = int(1e5);
  316.     cout << n << " " << m << " " << q << endl;
  317.     for (int i = 0; i < n; ++i) {
  318.         int x = 1e5 * cos(2 * pi / n * i);
  319.         int y = 1e5 * sin(2 * pi / n * i);
  320.         cout << x << " " << y << endl;
  321.     }
  322.     for (int i = 0; i < m; ++i) {
  323.         cout << i + 1 << " " << (i + 1) % n + 1 << endl;
  324.     }
  325.     for (int i = 0; i < q; ++i) {
  326.         cout << get_rand(-1e5, 1e5) << " " << get_rand(-1e5, 1e5) << endl;
  327.     }
  328.     exit(0);
  329. }
  330.  
  331. int main() {
  332.     //gen();
  333. #ifdef LOCAL42
  334.     freopen("input.txt", "r", stdin);
  335.     freopen("output.txt", "w", stdout);
  336. #endif
  337.     cin >> n >> m >> k;
  338.     for (int i = 0; i < n; ++i) {
  339.         scanf("%d %d", &p[i].x, &p[i].y);
  340.     }
  341.     for (int i = 0; i < m; ++i) {
  342.         scanf("%d %d", u + i, v + i);
  343.         --u[i];
  344.         --v[i];
  345.     }
  346.     for (int i = 0; i < k; ++i) {
  347.         scanf("%d %d", &q[i].x, &q[i].y);
  348.     }
  349.     rotate();
  350.     cerr << "ROTATE" << endl;
  351.     del_bridge();
  352.     for (int i = 0; i < m; ++i) {
  353.         int a = u[i], b = v[i];
  354.         g[a].pb(mp(p[b] - p[a], b));
  355.         g[b].pb(mp(p[a] - p[b], a));
  356.     }
  357.     for (int i = 0; i < n; ++i) {
  358.         sort(all(g[i]));
  359.         for (int j = 0; j < sz(g[i]); ++j) {
  360.             num[mp(i, g[i][j].sc)] = j;
  361.         }
  362.     }
  363.     for (int i = 0; i < n; ++i) {
  364.         for (int j = 0; j < sz(g[i]); ++j) {
  365.             if (edges.find(mp(i, g[i][j].sc)) == edges.end()) {
  366.                 int a = i, b = g[i][j].sc;
  367.                 edges.insert(mp(a, b));
  368.                 lst.clear();
  369.                 lst.pb(mp(a, b));
  370.                 for (;;) {
  371.                     int pos = (num[mp(b, a)] - 1 + sz(g[b])) % sz(g[b]);
  372.                     int c = g[b][pos].sc;
  373.                     a = b;
  374.                     b = c;
  375.                     if (edges.find(mp(a, b)) != edges.end()) {
  376.                         break;
  377.                     }
  378.                     edges.insert(mp(a, b));
  379.                     lst.pb(mp(a, b));
  380.                 }
  381.                 ll s = 0;
  382.                 for (int z = 0; z < sz(lst); ++z) {
  383.                     s += vec(p[lst[z].fs], p[lst[z].sc]);
  384.                 }
  385.                 if (s >= 0) {
  386.                     continue;
  387.                 }
  388.                 for (int z = 0; z < sz(lst); ++z) {
  389.                     point a = p[lst[z].fs], b = p[lst[z].sc];
  390.                     int bal = -42;
  391.                     if (a.x > b.x) {
  392.                         bal = 1;
  393.                     } else {
  394.                         bal = -1;
  395.                     }
  396.                     if (a.x > b.x) {
  397.                         swap(a, b);
  398.                     }
  399.                     segs.pb(mp(a, b));
  400.                     events.pb(event(a.x, ADD, sz(segs) - 1, bal));
  401.                     events.pb(event(b.x, DEL, sz(segs) - 1, bal));
  402.                 }
  403.             }
  404.         }
  405.     }
  406.     for (int i = 0; i < k; ++i) {
  407.         events.pb(event(q[i].x, QUERY, i, -42));
  408.     }
  409.     sort(all(events));
  410.     int root = 0, sz = 0;
  411.     for (int i = 0; i < sz(events); ++i) {
  412.         if (events[i].t == ADD) {
  413.             int l, r;
  414.             split(root, events[i].num, events[i].x, l, r);
  415.             d[++sz] = new_node(events[i].num, events[i].bal);
  416.             node_num[events[i].num] = sz;
  417.             root = merge(l, merge(sz, r));
  418.         }
  419.         if (events[i].t == DEL) {
  420.             int v = node_num[events[i].num];
  421.             int pv = d[v].p;
  422.             if (pv == 0) {
  423.                 root = merge(d[v].l, d[v].r);
  424.             } else {
  425.                 if (d[pv].r == v) {
  426.                     d[pv].r = merge(d[v].l, d[v].r);
  427.                 } else {
  428.                     d[pv].l = merge(d[v].l, d[v].r);
  429.                 }
  430.                 v = pv;
  431.                 while (v) {
  432.                     pv = d[v].p;
  433.                     calc(v);
  434.                     v = pv;
  435.                 }
  436.             }
  437.         }
  438.         if (events[i].t == QUERY) {
  439.             int j = events[i].num;
  440.             segs.pb(mp(q[j], q[j] + point(1, 0)));
  441.             int l, r;
  442.             split(root, sz(segs) - 1, q[j].x, l, r);
  443.             if (l > 0 && d[l].sum_bal > 0) {
  444.                 ans[j] = true;
  445.             }
  446.             root = merge(l, r);
  447.             segs.pbk();
  448.         }
  449.     }
  450.     for (int i = 0; i < k; ++i) {
  451.         puts((ans[i] ? "Yes" : "No"));
  452.     }
  453.     return 0;
  454. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!