icpcarchive6041

gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define iter(v) __typeof((v).begin())
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;

const int N = 200005;
struct point {
    int x, y, id;
	point (){}
	point (int x, int y):x(x), y(y) {}
	bool operator / (point oth){
		return (ll)(x) * oth.y - (ll)(y) * oth.x > 0;
	}

	ll operator ^ (point oth) {
		return (ll)(x) * oth.y - (ll)(y) * oth.x;
	}

	point operator - (point oth) {
		return point(x - oth.x, y - oth.y);
	}
};

bool fitInRange(point o, point a, point b) {
	if (a.x > b.x) swap(a.x, b.x);
	if (a.y > b.y) swap(a.y, b.y);
	return a.x <= o.x && o.x <= b.x && a.y <= o.y && o.y <= b.y;
}

bool onSeg(point o, point a, point b) {
	return !((b - o) ^ (a - o)) && fitInRange(o, a, b);
}

bool inPoly(int n, point *p, point o) {
	bool ret = 0;
	rep (i, n) {
		point a = p[i], b = p[(i + 1) % n];
		if (onSeg(o, a, b)) return 1;
		if (a.y > b.y) swap(a, b);
		ret ^= a.y != b.y && a.y != o.y && a.y <= o.y && o.y <= b.y && ((b - a) / (o - a));
	}
	return ret;
}

ll sqr(ll x) {return x * x;}

ll dis(point a, point b) {
	return sqr(a.x - b.x) + sqr(a.y - b.y);
}

struct Node {
	Node *lc, *rc;
	point o;
	bool div, exist;
}pool[N], *null = &pool[0];

int n, r, poolCnt;
point a[N];
point b[25];
point c[N];
Node *root;

bool cmpX(point a, point b) {return a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.id < b.id);}
bool cmpY(point a, point b) {return a.y < b.y || (a.y == b.y && a.x < b.x) || (a.x == b.x && a.y == b.y && a.id < b.id);}
bool cmp(point a, point b, bool div) {return div ? cmpY(a, b) : cmpX(a, b);}

Node *build(point *a, int l, int r, bool div) {
	if (l > r) return null;
	int mid = (l + r) / 2;
	nth_element(a + l, a + mid, a + r + 1, div ? cmpY : cmpX);
	Node *p = &pool[poolCnt++];
	p->div = div;
	p->o = a[mid];
	p->exist = 1;
	p->lc = build(a, l, mid - 1, !div);
	p->rc = build(a, mid + 1, r, !div);
	return p;
}

ll ans;
point q, ret;

void getNearest(Node *p) {
	if (p == null) return;
	if (p->exist) {
		ll d = dis(p->o, q);
		if (d < ans || (d == ans && p->o.id < ret.id)) {
			ans = d;
			ret = p->o;
		}
	}
	if (cmp(q, p->o, p->div)) {
		getNearest(p->lc);
		if (!p->div ? sqr(p->o.x - q.x) <= ans : sqr(p->o.y - q.y) <= ans) {
			getNearest(p->rc);
		}
	} else {
		getNearest(p->rc);
		if (!p->div ? sqr(p->o.x - q.x) <= ans : sqr(p->o.y - q.y) <= ans) {
			getNearest(p->lc);
		}
	}
}

void erase(Node *p, point o) {
	if (p->o.id == o.id) {
		p->exist = 0;
		return;
	}
	if (cmp(o, p->o, p->div)) {
		erase(p->lc, o);
	} else {
		erase(p->rc, o);
	}
}

void insert(Node *p, point o) {
	if (p->o.id == o.id) {
		p->exist = 1;
		return;
	}
	if (cmp(o, p->o, p->div)) {
		insert(p->lc, o);
	} else {
		insert(p->rc, o);
	}
}

int main() {
	#ifdef cwj
	freopen("in", "r", stdin);
	#endif
	int Tc;
	scanf("%d", &Tc);
	rep (casei, Tc) {
		printf("Case #%d:\n", casei + 1);
		scanf("%d", &n);
		rep (i, n) {
			scanf("%d%d", &a[i].x, &a[i].y);
			a[i].id = i + 1;
		}
		scanf("%d", &r);
		rep (ri, r) {
			printf("Region %d\n", ri + 1);
			int m;
			scanf("%d", &m);
			rep (i, m) {
				scanf("%d%d", &b[i].x, &b[i].y);
			}
			int cn = 0;
			rep (i, n) {
				if (inPoly(m, b, a[i])) {
					c[cn++] = a[i];
				}
			}
			poolCnt = 1;
			root = build(c, 0, cn - 1, 0);
			int query;
			scanf("%d", &query);
			rep (i, query) {
				scanf("%d%d", &q.x, &q.y);
				ans = 1LL << 60;
				getNearest(root);
				printf("%d ", ret.id);
				point tmp = ret;
				erase(root, tmp);
				ans = 1LL << 60;
				getNearest(root);
				printf("%d\n", ret.id);
				insert(root, tmp);
			}
		}
	}
}