Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
icpcarchive6041
#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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment