Advertisement
Guest User

Untitled

a guest
Nov 5th, 2015
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <cstring>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <bitset>
  13. #include <queue>
  14. #include <deque>
  15. #include <complex>
  16.  
  17. using namespace std;
  18.  
  19. #define pb push_back
  20. #define mp make_pair
  21. #define fs first
  22. #define sc second
  23. #define pbk pop_back
  24. #define sz(s) ((int) (s).size())
  25. #define len(s) ((int) (s).size())
  26. #define all(x) (x).begin(), (x).end()
  27. #ifdef LOCAL42
  28. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  29. #else
  30. #define eprintf(...) 42
  31. #define cerr if (0) cerr
  32. #endif
  33. #if _WIN32 || __WIN32__ || _WIN64 || __WIN64__
  34. #define LLD "%I64d"
  35. #else
  36. #define LLD "%lld"
  37. #endif
  38. #define next _next
  39. #define prev _prev
  40. #define link _link
  41. #define rank _rank
  42. #define hash _hash
  43.  
  44. typedef long long ll;
  45. typedef long long llong;
  46. typedef long long int64;
  47. typedef unsigned int uint;
  48. typedef unsigned long long ull;
  49. typedef unsigned long long ullong;
  50. typedef unsigned long long lint;
  51. typedef vector<int> vi;
  52. typedef pair<int, int> pii;
  53. typedef long double ld;
  54.  
  55. const int inf = 1e9;
  56. const double eps = 1e-9;
  57. const double pi = 4 * atan(1.0);
  58.  
  59. struct vt {
  60.     int x, y;
  61.     inline vt(int _x, int _y) {
  62.         x = _x, y = _y;
  63.     }
  64.     vt() {}
  65.     inline friend vt operator -(vt a, vt b) {
  66.         return vt(a.x - b.x, a.y - b.y);
  67.     }
  68.     inline friend vt operator +(vt a, vt b) {
  69.         return vt(a.x + b.x, a.y + b.y);
  70.     }
  71.     inline friend int operator ^(vt a, vt b) {
  72.         return a.x * b.y - b.x * a.y;
  73.     }
  74.     inline friend bool operator ==(vt a, vt b) {
  75.         return a.x == b.x && a.y == b.y;
  76.     }
  77.     inline friend bool operator <(vt a, vt b) {
  78.         if (a.x != b.x)
  79.             return a.x < b.x;
  80.         else
  81.             return a.y < b.y;
  82.     }
  83. };
  84.  
  85. struct node {
  86.     vt V[3], x;
  87.     bool is_leaf;
  88.     node* E[3];
  89.     node(vt _a, vt _b, vt _c, vt _x) {
  90.         V[0] = _a;
  91.         V[1] = _b;
  92.         V[2] = _c;
  93.         x = _x;
  94.         is_leaf = false;
  95.         E[0] = E[1] = E[2] = NULL;
  96.     }
  97.     node(vt _a, vt _b, vt _c) {
  98.         V[0] = _a;
  99.         V[1] = _b;
  100.         V[2] = _c;
  101.         is_leaf = true;
  102.     }
  103.  
  104. };
  105.  
  106. inline bool in_triangle(vt a, vt b, vt c, vt x) {
  107.     return ((b - a) ^ (x - a)) >= 0 && ((c - b) ^ (x - b)) >= 0 && ((a - c) ^ (x - c)) >= 0;
  108. }
  109.  
  110. const int N = 100500;
  111.  
  112. int goes_to[N];
  113.  
  114. vt tmp[N];
  115.  
  116. node* build(vt a, vt b, vt c, vt* l, vt* r) {
  117.     assert(((b - a) ^ (c - b)) > 0);
  118.     if (l == r)
  119.         return new node(a, b, c);
  120.     vt x = l[rand() % (r - l)];
  121.     vt P[] = { a, b, c };
  122.  
  123.     int start[3] = { 0, 0, 0 };
  124.  
  125.  
  126.     for (int i = 0; i < r - l; i++) {
  127.         if (l[i] == x) {
  128.             goes_to[i] = -1;
  129.             continue;
  130.         }
  131.         vt y = l[i];
  132.         tmp[i] = y;
  133.         int can[] = { -1, -1, -1 };
  134.         int cpt = 0;
  135.         for (int j = 0; j < 3; j++) {
  136.             vt u = P[(j + 1) % 3];
  137.             vt v = P[(j + 2) % 3];
  138.             if (in_triangle(u, v, x, y))
  139.                 can[cpt++] = j;
  140.         }
  141.         assert(cpt > 0);
  142.         goes_to[i] = can[rand() % cpt];
  143.         start[goes_to[i]]++;
  144.     }
  145.     start[2] = start[0] + start[1];
  146.     start[1] = start[0];
  147.     start[0] = 0;
  148.     for (int i = 0; i < r - l; i++) {
  149.         if (goes_to[i] == -1)
  150.             continue;
  151.         l[start[goes_to[i]]++] = tmp[i];
  152.     }
  153.     node* ret = new node(a, b, c, x);
  154.     ret->E[0] = build(b, c, x, l, l + start[0]);
  155.     ret->E[1] = build(c, a, x, l + start[0], l + start[1]);
  156.     ret->E[2] = build(a, b, x, l + start[1], l + start[2]);
  157.     return ret;
  158. }
  159.  
  160. node* get(node* cur, vt y) {
  161.     while (true) {
  162.         if (cur->is_leaf)
  163.             return cur;
  164.         for (int i = 0; i < 3; i++)
  165.             if (in_triangle(cur->E[i]->V[0], cur->E[i]->V[1], cur->E[i]->V[2], y)) {
  166.                 cur = cur->E[i];
  167.                 break;
  168.             }
  169.     }
  170. }
  171.  
  172. vt P[N];
  173. node* roots[N];
  174.  
  175. map<vt, int> indices;
  176.  
  177. inline int calc(int x) {
  178.     if (x >= 0)
  179.         return x / 3;
  180.     else
  181.         return -((-x) / 3);
  182. }
  183.  
  184. int main() {
  185. #ifdef LOCAL42
  186. #define TASK "A"
  187.     freopen(TASK ".in", "r", stdin);
  188.     freopen(TASK ".out", "w", stdout);
  189. #endif
  190.     int n;
  191.     scanf("%d", &n);
  192.     int mnx = inf, mny = inf, mxx = -inf, mxy = -inf;
  193.     for (int i = 0; i < n; i++) {
  194.         int x, y;
  195.         scanf("%d %d", &x, &y);
  196.         P[i] = vt(x, y);
  197.         indices[P[i]] = i + 1;
  198.         mxx = max(mxx, x);
  199.         mxy = max(mxy, y);
  200.         mnx = min(mnx, x);
  201.         mny = min(mny, y);
  202.     }
  203.     swap(*min_element(P, P + n), P[0]);
  204.     sort(P + 1, P + n, [&](vt a, vt b) {
  205.         return ((a - P[0]) ^ (b - P[0])) > 0;
  206.     });
  207.     vector<pair<vt, int>> stack;
  208.     for (int i = 0; i < n; i++) {
  209.         vt z = P[i];
  210.         while (stack.size() >= 2) {
  211.             vt y = stack[(int)stack.size() - 1].first;
  212.             vt x = stack[(int)stack.size() - 2].first;
  213.             if (((y - x) ^ (z - y)) <= 0)
  214.                 stack.pop_back();
  215.             else
  216.                 break;
  217.         }
  218.         stack.push_back(make_pair(z, i));
  219.     }
  220.     int rpt = 0;
  221.     for (int i = 1; i + 1 < stack.size(); i++) {
  222.         vt a = stack[0].first;
  223.         vt b = stack[i].first;
  224.         vt c = stack[i + 1].first;
  225.         roots[rpt++] = build(a, b, c, P + stack[i].second + 1, P + stack[i + 1].second);
  226.     }
  227.  
  228.     int k;
  229.     vt q;
  230.     scanf("%d %d %d", &k, &q.x, &q.y);
  231.     int w = mxx - mnx;
  232.     int h = mxy - mny;
  233.     for (int i = 0; i < k; i++) {
  234.         int l = -1;
  235.         int r = rpt;
  236.         while (r - l > 1) {
  237.             int m = (l + r) / 2;
  238.             vt a, b, c;
  239.             a = roots[m]->V[0];
  240.             b = roots[m]->V[1];
  241.             c = roots[m]->V[2];
  242.             if (((b - a) ^ (q - a)) < 0)
  243.                 r = m;
  244.             else
  245.                 l = m;
  246.         }
  247.         assert(l != -1);
  248.         node* res = get(roots[l], q);
  249.         printf("%d", 3);
  250.         vt sum(0, 0);
  251.         for (int j = 2; j >= 0; j--) {
  252.             printf(" %d", indices[res->V[j]]);
  253.             sum = sum + res->V[j];
  254.         }
  255.         sum.x = calc(sum.x);
  256.         sum.y = calc(sum.y);
  257.         int dx, dy;
  258.         scanf("%d %d", &dx, &dy);
  259.         dx += sum.x;
  260.         dy += sum.y;
  261.         dx = (dx % w + w) % w;
  262.         dy = (dy % h + h) % h;
  263.         q = vt(mnx + dx, mny + dy);
  264.         printf("\n");
  265.     }
  266.     return 0;
  267. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement