【LG3249】[HNOI2016]矿区

题面

洛谷

题解

先平面图转对偶图，

建好了对偶图之后随意拿出一个生成树，以无边界的范围为根。

无边界的范围很好求，用叉积算出有向面积时，算出来是负数的就是无边界的范围。

然后标记所有的树边，记录生成树中每个子树的矿区面积和及面积平方和。

对于每一个询问，先找到询问里出现的边，如果有非树边就忽略，否则如果这条边所在的面是儿子，就加上子树的面积，如果是父亲就减去儿子子树的面积。

这个可以通过画图手玩进行证明。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 2e5 + 5, MAX_M = 1.2e6 + 5;

const double EPS = 1e-10;

struct Point { int x, y; } p[MAX_N];

Point operator - (const Point &l, const Point &r) { return (Point){l.x - r.x, l.y - r.y}; }

long long cross(const Point &l, const Point &r) { return 1ll * l.x * r.y - 1ll * l.y * r.x; }

struct Edge { int id, x, y; double a; } e[MAX_M]; int e_cnt = 0;

bool operator < (const Edge &l, const Edge &r)

    { return fabs(l.a - r.a) < EPS ? l.y < r.y : l.a < r.a; }

vector<Edge> G[MAX_N], T[MAX_M];

void Add_Edge(int u, int v) {

	e[e_cnt] = (Edge){e_cnt, u, v, atan2(p[v].y - p[u].y, p[v].x - p[u].x)};

	G[u].push_back(e[e_cnt]); e_cnt++;

}

int N, M, Q;

int cnt, root, nxt[MAX_M], pos[MAX_M], fa[MAX_M];

long long ans1, ans2, s1[MAX_M], s2[MAX_M];

void build() {

	for (int i = 1; i <= N; i++) sort(G[i].begin(), G[i].end());

	for (int i = 0; i < e_cnt; i++) {

		int y = e[i].y;

		vector<Edge> :: iterator ite = lower_bound(G[y].begin(), G[y].end(), e[i ^ 1]);

		if (ite == G[y].begin()) ite = G[y].end();

		--ite, nxt[i] = ite -> id;

	}

	for (int i = 0; i < e_cnt; i++) {

		if (pos[i]) continue;

		pos[i] = pos[nxt[i]] = ++cnt;

		for (int j = nxt[i]; e[j].y != e[i].x; j = nxt[j], pos[j] = cnt)

			s1[cnt] += cross(p[e[j].x] - p[e[i].x], p[e[j].y] - p[e[i].x]);

		if (s1[cnt] <= 0) root = cnt;

	}

	for (int i = 0; i < e_cnt; i++)

		T[pos[i]].push_back((Edge){i, pos[i], pos[i ^ 1]});

}

bool vis[MAX_M], ist[MAX_M];

void dfs(int x) {

	s2[x] = 1ll * s1[x] * s1[x], s1[x] <<= 1ll, vis[x] = 1;

	for (int i = 0, sz = T[x].size(); i < sz; i++) {

		int y = T[x][i].y; if (vis[y]) continue;

		ist[T[x][i].id] = ist[T[x][i].id ^ 1] = 1;

		fa[y] = x; dfs(y); s1[x] += s1[y], s2[x] += s2[y];

	}

}

long long gcd(long long x, long long y) {

	if (y == 0) return x;

	else return gcd(y, x % y);

}

int q[MAX_M];

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	N = gi(), M = gi(), Q = gi();

	for (int i = 1; i <= N; i++) p[i] = (Point){gi(), gi()};

	for (int i = 1; i <= M; i++) {

		int u = gi(), v = gi();

		Add_Edge(u, v), Add_Edge(v, u);

	}

	build(); dfs(root);

	while (Q--) {

		int n = (gi() + ans1) % N + 1;

		for (int i = 1; i <= n; i++) q[i] = (gi() + ans1) % N + 1;

		q[n + 1] = q[1], ans1 = ans2 = 0;

		for (int i = 1; i <= n; i++) {

			int x = q[i], y = q[i + 1];

			Edge e = (Edge){0, x, y, atan2(p[y].y - p[x].y, p[y].x - p[x].x)};

			vector<Edge> :: iterator ite = lower_bound(G[x].begin(), G[x].end(), e);

			int j = ite -> id; if (!ist[j]) continue;

			if (fa[pos[j]] == pos[j ^ 1]) ans1 += s2[pos[j]], ans2 += s1[pos[j]];

			else ans1 -= s2[pos[j ^ 1]], ans2 -= s1[pos[j ^ 1]];

		}

		long long tmp = gcd(ans1, ans2);

		ans1 /= tmp, ans2 /= tmp;

		printf("%lld %lld\n", ans1, ans2);

	}

    return 0;

}