首页 > 代码库 > 4541: [Hnoi2016]矿区
4541: [Hnoi2016]矿区
学习了一下平面图剖分的姿势,orz cbh
每次只要随便选择一条边,然后不停尽量向左转就行
#include <bits/stdc++.h>#define N 1300000#define M 5000013#define LL long long#define pb push_backusing namespace std;LL n, m, k;struct point { LL x, y;} S[N];vector <LL> bi[N];vector <LL> re[N], vis[N], s1[N], s2[N];vector <LL> bt[N], ca[N], cb[N];LL tot_are;LL siz[N], sum1[N], sum2[N], tot[N];LL nwc;LL comp(LL a, LL b){ return atan2(S[a].y - S[nwc].y, S[a].x - S[nwc].x) > atan2(S[b].y - S[nwc].y, S[b].x - S[nwc].x);}LL getsiz(point a, point b, point c){ return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);} namespace addr{ LL hs[M]; LL dt[M]; LL get(LL a, LL b) { return 1ll * a * 1000000 + b; } LL & find(LL a, LL b) { LL p = get(a, b); LL q = p % M; while (hs[q] && hs[q] != p) q = (q + 1) % M; hs[q] = p; return dt[q]; }}LL tvis[N], fa[N];void dfs(LL t){ //cout << t << "\n"; tvis[t] = 1; sum1[t] = siz[t] * siz[t]; sum2[t] = siz[t] * 2; for (LL i = 0; i < bt[t].size(); ++ i) if (!tvis[bt[t][i]]) { dfs(bt[t][i]); fa[bt[t][i]] = t; sum1[t] += sum1[bt[t][i]]; sum2[t] += sum2[bt[t][i]]; s1[ca[t][i]][addr :: find(ca[t][i], cb[t][i])] = sum1[bt[t][i]]; s2[ca[t][i]][addr :: find(ca[t][i], cb[t][i])] = sum2[bt[t][i]]; s1[cb[t][i]][addr :: find(cb[t][i], ca[t][i])] = -sum1[bt[t][i]]; s2[cb[t][i]][addr :: find(cb[t][i], ca[t][i])] = -sum2[bt[t][i]]; }}LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}LL c = 0;int main(){ //freopen("mine2.in", "r", stdin); n = read(); m = read(); k = read(); for (LL i = 1; i <= n; ++ i) S[i].x = read(), S[i].y = read(); for (LL i = 1; i <= m; ++ i) { LL a, b; a = read(); b = read(); bi[a].push_back(b); bi[b].push_back(a); } for (LL i = 1; i <= n; ++ i) re[i].resize(bi[i].size()), s1[i] = s2[i] = vis[i] = re[i]; for (LL i = 1; i <= n; ++ i) nwc = i, sort(bi[i].begin(), bi[i].end(), comp); for (LL i = 1; i <= n; ++ i) for (LL j = 0; j < bi[i].size(); ++ j) addr :: find(i, bi[i][j]) = j; for (LL i = 1; i <= n; ++ i) for (LL j = 0; j < bi[i].size(); ++ j) re[i][j] = addr :: find(bi[i][j], i); for (LL i = 1; i <= n; ++ i) for (LL j = 0; j < bi[i].size(); ++ j) if (!vis[i][j]) { tot_are ++; for (LL k = i, p = j; !vis[k][p]; ) { siz[tot_are] += getsiz(S[i], S[k], S[bi[k][p]]); vis[k][p] = tot_are; LL np = (re[k][p] + 1) % bi[bi[k][p]].size(); k = bi[k][p]; p = np; } if (siz[tot_are] < 0) c = tot_are; } for (LL i = 1; i <= n; ++ i) for (LL j = 0; j < bi[i].size(); ++ j) bt[vis[i][j]].push_back(vis[bi[i][j]][re[i][j]]), ca[vis[i][j]].push_back(i), cb[vis[i][j]].push_back(bi[i][j]); dfs(c); for (LL i = 1, last = 0; i <= k; ++ i) { LL d, ns1 = 0, ns2 = 0; d = read(); d = (d + last) % n + 1; LL fs, ls, nw; fs = read(); fs = (fs + last) % n + 1; ls = fs; for (LL j = 2; j <= d; ++ j, ls = nw) { nw = read(); nw = (nw + last) % n + 1; ns1 += s1[ls][addr :: find(ls, nw)]; ns2 += s2[ls][addr :: find(ls, nw)]; } ns1 += s1[ls][addr :: find(ls, fs)]; ns2 += s2[ls][addr :: find(ls, fs)]; LL g = __gcd(ns1, ns2); cout << ns1 / g << " " << ns2 / g << "\n"; last = ns1 / g; }}
放在class里的东西还会爆栈QAQ,以后不敢用了
4541: [Hnoi2016]矿区
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。