C++11(clang++ 3.9) 解法, 执行用时: 1819ms, 内存消耗: 73696K, 提交时间: 2019-01-07 19:29:00

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define CLOCKWISE 1
#define ANTICLOCKWISE -1
#define LEFT_CONVEX 1
#define RIGHT_CONVEX -1
#define CONSTRUCT_LAYERS 1
#define SINGLE_QUERY -1
#define MAX_N 100000
#define MAX_LAYERS 100
#define INF (~0U>>1)
using namespace std;

struct Point {
 int x, y;
 int layer, pos;
 int idx;
};
long long cx(Point *a, Point *b, Point *c) {
 return (long long) (b->x-a->x)*(c->y-a->y) - (long long) (b->y-a->y)*(c->x-a->x);
}
long long dj(Point *a, Point *b, Point *c) {
 return (long long) (b->x-a->x)*(c->x-a->x) + (long long) (b->y-a->y)*(c->y-a->y);
}
struct Hull {
 Point **p;
 int n;
 Hull (int n) {
  p = (Point **) malloc(sizeof(Point *) * (n+2));
  this->n = n;
 }
 Point *pos(int x) { while (x <= 0) x += n; while (x >= n) x -= n; return p[x]; }
};
struct Convex {
 Point **p;
 int h, t;
 int sign;
 bool refine(Point *a) { bool dom = false; while (h < t && cx(p[t-1], p[t], a) * sign >= 0) --t, dom = true; return dom; }
 void push(Point *a)   { refine(a); p[++t] = a; }
 Point *peek()     { return h == t ? NULL : p[h+1]; }
 Point *pop()          { return p[++h]; }
 Point *top()    { return p[t]; }
};
struct Opening {
 Point *a, *b;
 int apos, bpos;
 Convex *a_con, *b_con;
};
struct Segment {
 int l, r;
};

long long *v[MAX_LAYERS+10];
long long area;
int removed[MAX_N+10];
int idx[MAX_N+10];

Point *o;
Point *p[MAX_N+10], *p2[MAX_N+10], *q[MAX_N+10], *rp[MAX_N+10];
Point **point_heap;
int p_point_heap;

Hull *layer[MAX_LAYERS+10];

Opening *opening[MAX_LAYERS+10];
Opening **s_op, **t_op, **n_op;
Opening *open;

Convex *convex[MAX_LAYERS+10];
int n_convex;

Segment segment[MAX_LAYERS+10];

bool cmp_pointrp(Point *a, Point *b) {
 return a->layer == b->layer ? a->pos < b->pos : a->layer < b->layer;
}
bool cmp_point2d(Point *a, Point *b) {
 return a->x == b->x ? a->y < b->y : a->x < b->x;
}
bool cmp_opening(Opening *a, Opening *b) {
 return a->apos < b->apos;
}
void init() {
 o = new Point();
 o->x = o->y = 0;
 point_heap = (Point **) malloc(sizeof(Point*) * (4 * MAX_LAYERS * MAX_LAYERS));
 open = new Opening();
 open->apos = -INF;
 open->bpos = INF;
}
void clear_for_query() {
    opening[0] = open;
 s_op = n_op = opening;
 t_op = s_op+1;
 p_point_heap = 0;
 area = v[1][0];
}
Point **point_malloc(int n) {
 Point **p = point_heap + (p_point_heap);
 p_point_heap += n;
 return p;
}
Convex *new_convex(int sign, Point *a) {
 Convex *con = new Convex();
 con->p = point_malloc(MAX_LAYERS+2);
 con->h = 1, con->t = 0;
 con->sign = sign;
 con->push(a);
 return con;
}
Opening *new_opening(Point *a, Point *b, Point *pa, Point *pb, Convex *a_con, Convex *b_con) {
 Opening *op = new Opening();
 op->a = a, op->b = b;
 op->apos = pa->pos, op->bpos = pb->pos;
 op->a_con = a_con;
 op->b_con = b_con;
 if (op->apos > op->bpos)
  op->bpos += layer[pa->layer]->n;
 return op;
}
long long cxsum(Point *a, Point *b) {
 long long *vp = v[a->layer];
 return a->pos <= b->pos ? vp[b->pos]-vp[a->pos] : vp[0] - (vp[a->pos]-vp[b->pos]);
}
Point *find_tangle(Hull *hull, Point *a, int sign) {
 int n = hull->n;
 int bias = sign == -1;
 if (n == 0)
  return NULL;
 if (n == 1)
  return hull->p[n];
 
 Point *b = hull->pos(sign+bias);

 bool dom = cx(a, hull->pos(sign+bias), hull->pos(bias)) * sign <= 0;
 int l = 2, r = n, j, an = 1;
 
 for (; j = (l+r)>>1, l <= r; ) {
  if (cx(a, b, hull->pos(sign*j+bias)) * sign <= 0) {
   if (dom) r = j-1;
   else l = j+1;
  }
  else if (cx(a, hull->pos(sign*j+bias), hull->pos(sign*(j-1)+bias)) * sign <= 0)
   an = j, l = j+1;
  else r = j-1;
 } return hull->pos(sign*an+bias);
}
bool find_new_opening(Hull *hull, Point *a, Point *b, Convex *a_con, Convex *b_con) {
 Point *s1 = a, *s2 = b;
 Point *pa, *pb;
 while (a->idx != b->idx) {
  pa = find_tangle(hull, a, CLOCKWISE);
  pb = find_tangle(hull, b, ANTICLOCKWISE);

  if (a_con->peek() && (pa == NULL || cx(a, pa, a_con->peek()) >= 0)) {
   area += cx(o, a, a_con->peek());
   a = a_con->pop();
  }
  else if (b_con->peek() && (pb == NULL || cx(b, b_con->peek(), pb) >= 0)) {
   area += cx(o, b_con->peek(), b);
   b = b_con->pop();
  }
  else {
   area += cx(o, a, pa) + cx(o, pb, b) + cxsum(pa, pb);
   *(++n_op) = new_opening(a, b, pa, pb, a_con, b_con);
   return 1;
  }
 }
 return 0;
}
void layer_by_layer(int m, Point **rp) {
 Point *a, *b, *ia, *ib, *a_del, *b_del;
 Convex *a_con, *b_con;
 Segment *seg_s, *seg, *seg_end;
 Hull *cur, *hull;
 sort(rp+1, rp+m+1, cmp_pointrp);
 int s = 1, t;

    int num = 0;
    Point *record = NULL;
    Point *pa, *pb;

 for (int i = 1; i <= MAX_LAYERS; ++i, s = t) {
  cur = layer[i], hull = layer[i+1];

        if (num == 1) {
            pa = find_tangle(cur, record, CLOCKWISE);
            pb = find_tangle(cur, record, ANTICLOCKWISE);
            *s_op = new_opening(record, record, pa, pb, new_convex(LEFT_CONVEX, record), new_convex(RIGHT_CONVEX, record));
            area = cxsum(pa, pb) + cx(o, record, pa) + cx(o, pb, record);
        }

  if (s > m || rp[s]->layer != i)
   break;
  t = s;
  while (t <= m && rp[t]->layer == rp[s]->layer)
   ++t;

        if (t == s) {
            break;
        }
        if (cur->n - (t-s) == 1 && num == 0) {
            num = 1;
            for (int j = 0; j < cur->n; ++j)
                if (removed[cur->p[j]->idx] == false) {
                    record = cur->p[j];
                    break;
                }
            continue;
        }
        if (cur->n - (t-s) == 0 && num == 0) {
            area = v[i+1][0];
            continue;
        }

  if (t - s == cur->n) {
            if (num == 1)
                continue;
   for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
    Opening *op = *p_op;
    area -= cx(o, op->a, cur->pos(op->apos));
    area -= cx(o, cur->pos(op->bpos), op->b);
    area -= cxsum(cur->pos(op->apos), cur->pos(op->bpos));
    find_new_opening(hull, op->a, op->b, op->a_con, op->b_con);
   }
   s_op = t_op;
   t_op = n_op + 1;
   sort(s_op, t_op, cmp_opening);
   continue;
  }

  seg_s = seg = segment;
  for (int j = s+1; j < t; ++j)
   if (rp[j]->pos != rp[j-1]->pos+1) {
    seg->r = rp[j-1]->pos;
    (++seg)->l = rp[j]->pos;
   }
  if (rp[s]->pos == 1 && rp[t-1]->pos == cur->n) {
   seg_s->l = seg->l - cur->n;
   --seg;
  }
  else seg_s->l = rp[s]->pos, seg->r = rp[t-1]->pos;
  int n_seg = seg-seg_s+1;
  
  while (seg->r < 2*cur->n) {
   ++seg;
   seg->r = (seg-n_seg)->r + cur->n;
   seg->l = (seg-n_seg)->l + cur->n;
  }
  if (num <= 0) seg_end = seg_s + n_seg;
  else seg_end = seg+1;
  seg = seg_s;

  for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
   Opening *op = *p_op; 
   while (seg != seg_end && seg->r < op->apos)
    ++seg;
   while (seg != seg_end && seg->l <= op->bpos) {
    ia = cur->pos(seg->l-1);
    ib = cur->pos(seg->r+1);

    if (seg->l <= op->apos) {
     a = op->a, a_con = op->a_con;
     a_del = cur->pos(op->apos);
     area -= cx(o, a, a_del);
    }
    else {
     a = ia, a_con = new_convex(LEFT_CONVEX, a);
     a_del = ia;
    }
    if (seg->r >= op->bpos) {
     b = op->b, b_con = op->b_con;
     b_del = cur->pos(op->bpos);
     area -= cx(o, b_del, b);
    }
    else {
     b = ib, b_con = new_convex(RIGHT_CONVEX, b);
     b_del = ib;
    }
    if (b == ib) {
     while (a_con->h < a_con->t && cx(a, b, a_con->top()) <= 0) --a_con->t;
     a_con->push(b);
    }
    else if (a == ia) {
     while (b_con->h < b_con->t && cx(a, b, b_con->top()) <= 0) --b_con->t;
     b_con->push(a);
    }
    if (cx(a, b, ia) > 0 && (a_con->refine(ia) || b_con->refine(ia)))
     a_con->push(ia), b_con->push(ia);
    if (cx(a, b, ib) > 0 && (a_con->refine(ib) || b_con->refine(ib)))
     b_con->push(ib), a_con->push(ib);
    area -= cxsum(a_del, b_del);
   
    find_new_opening(hull, a, b, a_con, b_con);
    
    if (seg->r >= op->bpos)
     break;
    ++seg;
   }
  }
        num += cur->n - (t-s);
  s_op = t_op;
  t_op = n_op + 1;
  sort(s_op, t_op, cmp_opening);
 }
}
void bruteforce(int n, Point **p, int &t, Point **q, int mode) {
 int h;
 h = 1, t = 0;
 for (int i = 1; i <= n; ++i) {
  if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
   continue;
  if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
   continue;
  while (t > 1 && cx(q[t-1], q[t], p[i]) >= 0) --t;
  q[++t] = p[i];
 }
 h = t, --t;
 for (int i = n; i >= 1; --i) {
  if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
   continue;
  if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
   continue;
  while (h < t && cx(q[t-1], q[t], p[i]) >= 0) --t;
  q[++t] = p[i];
 }
 if (t == 1) t = 2, q[t+1] = q[1];
 if (t <= 0) t = 1;
}
void construct_layers(int n, Point **p, Point **q) {
 int t;
 sort(p+1, p+n+1, cmp_point2d);
 for (int i = 1; i <= MAX_LAYERS+1; ++i) {
  bruteforce(n, p, t, q, CONSTRUCT_LAYERS);
  Hull *hull = new Hull(t-1);
  layer[i] = hull;
  if (t == 1)
   break;
  for (int j = 1; j < t; ++j) {
   q[j]->layer = i;
   q[j]->pos = j;
   hull->p[j] = q[j];
  }
  hull->p[0] = hull->p[t-1];
  hull->p[t] = hull->p[1];
  long long *vp = (long long *) malloc(sizeof(long long)*(t+2));
  for (int j = 1; j <= t; ++j)
   vp[j] = j == 1 ? 0 : vp[j-1] + cx(o, q[j-1], q[j]);
  vp[0] = vp[t];
  v[i] = vp;
 }
}
int main() {
 init();
 int n, m;
 cin >> n >> m;
 for (int i = 1; i <= n; ++i) {
  int x, y;
  Point *pt = new Point();
  scanf("%d %d", &x, &y);
  pt->x = x, pt->y = y;
  pt->idx = i;
  p[i] = p2[i] = pt;
 }
 construct_layers(n, p2, q);
 for (int i = 1; i <= m; ++i) {
  int rc = i == 1 ? (n-1) : (-area) % n;
  clear_for_query();

  int x, k, t = 0;
  scanf("%d", &k);
  for (int j = 1; j <= k; ++j) {
   scanf("%d", idx+j);
   idx[j] = (idx[j] + 1LL*rc) % n + 1;
   
            if (removed[idx[j]] == true)
    continue;
   removed[idx[j]] = true;
   
            if (p[idx[j]]->layer != 0)
    rp[++t] = p[idx[j]];
  }

        layer_by_layer(t, rp);

  for (int j = 1; j <= k; ++j)
            removed[idx[j]] = false;

  cout << -area << endl;
 }
}