Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <ctime>
- #include <cstring>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <bitset>
- #include <queue>
- #include <deque>
- #include <complex>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define fs first
- #define sc second
- #define pbk pop_back
- #define sz(s) ((int) (s).size())
- #define len(s) ((int) (s).size())
- #define all(x) (x).begin(), (x).end()
- #ifdef LOCAL42
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...) 42
- #define cerr if (0) cerr
- #endif
- #if _WIN32 || __WIN32__ || _WIN64 || __WIN64__
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- #define next _next
- #define prev _prev
- #define link _link
- #define rank _rank
- #define hash _hash
- typedef long long ll;
- typedef long long llong;
- typedef long long int64;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef unsigned long long ullong;
- typedef unsigned long long lint;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- typedef long double ld;
- const int inf = 1e9;
- const double eps = 1e-9;
- const double pi = 4 * atan(1.0);
- struct vt {
- int x, y;
- inline vt(int _x, int _y) {
- x = _x, y = _y;
- }
- vt() {}
- inline friend vt operator -(vt a, vt b) {
- return vt(a.x - b.x, a.y - b.y);
- }
- inline friend vt operator +(vt a, vt b) {
- return vt(a.x + b.x, a.y + b.y);
- }
- inline friend int operator ^(vt a, vt b) {
- return a.x * b.y - b.x * a.y;
- }
- inline friend bool operator ==(vt a, vt b) {
- return a.x == b.x && a.y == b.y;
- }
- inline friend bool operator <(vt a, vt b) {
- if (a.x != b.x)
- return a.x < b.x;
- else
- return a.y < b.y;
- }
- };
- struct node {
- vt V[3], x;
- bool is_leaf;
- node* E[3];
- node(vt _a, vt _b, vt _c, vt _x) {
- V[0] = _a;
- V[1] = _b;
- V[2] = _c;
- x = _x;
- is_leaf = false;
- E[0] = E[1] = E[2] = NULL;
- }
- node(vt _a, vt _b, vt _c) {
- V[0] = _a;
- V[1] = _b;
- V[2] = _c;
- is_leaf = true;
- }
- };
- inline bool in_triangle(vt a, vt b, vt c, vt x) {
- return ((b - a) ^ (x - a)) >= 0 && ((c - b) ^ (x - b)) >= 0 && ((a - c) ^ (x - c)) >= 0;
- }
- const int N = 100500;
- int goes_to[N];
- vt tmp[N];
- node* build(vt a, vt b, vt c, vt* l, vt* r) {
- assert(((b - a) ^ (c - b)) > 0);
- if (l == r)
- return new node(a, b, c);
- vt x = l[rand() % (r - l)];
- vt P[] = { a, b, c };
- int start[3] = { 0, 0, 0 };
- for (int i = 0; i < r - l; i++) {
- if (l[i] == x) {
- goes_to[i] = -1;
- continue;
- }
- vt y = l[i];
- tmp[i] = y;
- int can[] = { -1, -1, -1 };
- int cpt = 0;
- for (int j = 0; j < 3; j++) {
- vt u = P[(j + 1) % 3];
- vt v = P[(j + 2) % 3];
- if (in_triangle(u, v, x, y))
- can[cpt++] = j;
- }
- assert(cpt > 0);
- goes_to[i] = can[rand() % cpt];
- start[goes_to[i]]++;
- }
- start[2] = start[0] + start[1];
- start[1] = start[0];
- start[0] = 0;
- for (int i = 0; i < r - l; i++) {
- if (goes_to[i] == -1)
- continue;
- l[start[goes_to[i]]++] = tmp[i];
- }
- node* ret = new node(a, b, c, x);
- ret->E[0] = build(b, c, x, l, l + start[0]);
- ret->E[1] = build(c, a, x, l + start[0], l + start[1]);
- ret->E[2] = build(a, b, x, l + start[1], l + start[2]);
- return ret;
- }
- node* get(node* cur, vt y) {
- while (true) {
- if (cur->is_leaf)
- return cur;
- for (int i = 0; i < 3; i++)
- if (in_triangle(cur->E[i]->V[0], cur->E[i]->V[1], cur->E[i]->V[2], y)) {
- cur = cur->E[i];
- break;
- }
- }
- }
- vt P[N];
- node* roots[N];
- map<vt, int> indices;
- inline int calc(int x) {
- if (x >= 0)
- return x / 3;
- else
- return -((-x) / 3);
- }
- int main() {
- #ifdef LOCAL42
- #define TASK "A"
- freopen(TASK ".in", "r", stdin);
- freopen(TASK ".out", "w", stdout);
- #endif
- int n;
- scanf("%d", &n);
- int mnx = inf, mny = inf, mxx = -inf, mxy = -inf;
- for (int i = 0; i < n; i++) {
- int x, y;
- scanf("%d %d", &x, &y);
- P[i] = vt(x, y);
- indices[P[i]] = i + 1;
- mxx = max(mxx, x);
- mxy = max(mxy, y);
- mnx = min(mnx, x);
- mny = min(mny, y);
- }
- swap(*min_element(P, P + n), P[0]);
- sort(P + 1, P + n, [&](vt a, vt b) {
- return ((a - P[0]) ^ (b - P[0])) > 0;
- });
- vector<pair<vt, int>> stack;
- for (int i = 0; i < n; i++) {
- vt z = P[i];
- while (stack.size() >= 2) {
- vt y = stack[(int)stack.size() - 1].first;
- vt x = stack[(int)stack.size() - 2].first;
- if (((y - x) ^ (z - y)) <= 0)
- stack.pop_back();
- else
- break;
- }
- stack.push_back(make_pair(z, i));
- }
- int rpt = 0;
- for (int i = 1; i + 1 < stack.size(); i++) {
- vt a = stack[0].first;
- vt b = stack[i].first;
- vt c = stack[i + 1].first;
- roots[rpt++] = build(a, b, c, P + stack[i].second + 1, P + stack[i + 1].second);
- }
- int k;
- vt q;
- scanf("%d %d %d", &k, &q.x, &q.y);
- int w = mxx - mnx;
- int h = mxy - mny;
- for (int i = 0; i < k; i++) {
- int l = -1;
- int r = rpt;
- while (r - l > 1) {
- int m = (l + r) / 2;
- vt a, b, c;
- a = roots[m]->V[0];
- b = roots[m]->V[1];
- c = roots[m]->V[2];
- if (((b - a) ^ (q - a)) < 0)
- r = m;
- else
- l = m;
- }
- assert(l != -1);
- node* res = get(roots[l], q);
- printf("%d", 3);
- vt sum(0, 0);
- for (int j = 2; j >= 0; j--) {
- printf(" %d", indices[res->V[j]]);
- sum = sum + res->V[j];
- }
- sum.x = calc(sum.x);
- sum.y = calc(sum.y);
- int dx, dy;
- scanf("%d %d", &dx, &dy);
- dx += sum.x;
- dy += sum.y;
- dx = (dx % w + w) % w;
- dy = (dy % h + h) % h;
- q = vt(mnx + dx, mny + dy);
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement