首页 > 代码库 > [BZOJ2391]Cirno的忧郁
[BZOJ2391]Cirno的忧郁
[BZOJ2391]Cirno的忧郁
试题描述
Cirno闲着无事的时候喜欢冰冻青蛙。
Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形,Cirno运用自己的能力能将此多边形内所有青蛙冰冻。
雾之湖生活着m只青蛙,青蛙有大有小,所以每只青蛙的价值为一个不大于10000的正整数。
Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限,Cirno将这个问题交给完美算术教室里的你。
因为爱护动物,所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。
输入
第一行2个正整数 n,m。
以下n行,每行2个整数xi,yi,表示第i个结点的坐标。
再以下m行,每行3个整数xj,yj,vj,表示第j个青蛙的坐标和价值。
第n+m+1行一个整数q,表示有q组询问。
每组询问有2行,第一行一个整数s(3<=s<=n),表示简单多边形的结点数。第二行s个正整数,顺时针或逆时针给出多边形的结点的编号(1--n)
输出
q行。
对于每个询问,每行输出一个整数表示冻结的青蛙的价值之和
输入示例
4 3 2 2 3 5 7 4 5 1 3 4 2 4 3 7 6 3 90 2 3 1 2 3 4 1 4 3 2
输出示例
9 99
数据规模及约定
对于30%的数据,n,m<=100; q<=100
对于60%的数据,n,m<=100; q<=10000
对于100%的数据,n,m<=1000; q<=10000
-10000<=x,y<=10000; 0<v<=10000
题解
向量真是太好使了!
首先介绍一个新东西:三角剖分。拿此题为例,我们把两类点混成一类,只是第一类点权值为 0。接下来,给所有点按照极角坐标排序,那么我们需要维护一个 tot[i][j] 表示原点、i、j 这三个点所构成的三角形包含的点的权值和,并且规定:i 到 j 是极角排序正方向时 tot[i][j] 为正(注意所有权值 v > 0),反之为负。那么在询问时对于一个简单多边形直接把相邻两个顶点的 tot 值累加起来即可。
至于如何维护 tot[i][j],可以先确定 i 并以点 i 作为新的原点,然后按极角的顺序一个一个往平衡树内加点,每次加点 j 时统计一下当前平衡树内以 i 为原点且在向量 i->j 左的向量有多少个,这个个数就是 tot[i][j]。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #include <cmath> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 2010 struct Vec { int x, y; Vec() {} Vec(int _, int __): x(_), y(__) {} bool operator < (const Vec& t) const { return t.y * x - t.x * y ? t.y * x - t.x * y < 0 : x * x + y * y > t.x * t.x + t.y * t.y; } // if a < b then a is on b‘s left side. Vec operator - (const Vec& t) const { return Vec(x - t.x, y - t.y); } } st; struct Point { Vec p; int val, id; Point() {} Point(Vec _1, int _2, int _3): p(_1), val(_2), id(_3) {} bool operator < (const Point& t) const { return p - st < t.p - st; } } ps[maxn]; int cp; struct Node { Vec v; int val, r, siz, sum; Node() {} Node(Vec _1, int _2, int _3): v(_1), val(_2), r(_3) {} } ns[maxn]; int ToT, rt, fa[maxn], ch[2][maxn]; void maintain(int o) { ns[o].siz = 1; ns[o].sum = ns[o].val; for(int i = 0; i < 2; i++) if(ch[i][o]) ns[o].siz += ns[ch[i][o]].siz, ns[o].sum += ns[ch[i][o]].sum; return ; } void rotate(int u) { int y = fa[u], z = fa[y], l = 0, r = 1; if(z) ch[ch[1][z]==y][z] = u; if(ch[1][y] == u) swap(l, r); fa[u] = z; fa[y] = u; fa[ch[r][u]] = y; ch[l][y] = ch[r][u]; ch[r][u] = y; maintain(y); maintain(u); return ; } int insert(int& o, Point x, Point Org) { if(!o) { ns[o = ++ToT] = Node(x.p, x.val, rand()); maintain(o); return x.val; } bool d = x.p - Org.p < ns[o].v - Org.p; d ^= 1; int ans = 0, ls = ch[0][o] ? ns[ch[0][o]].sum : 0; if(d) ans += ls + ns[o].val; ans += insert(ch[d][o], x, Org); fa[ch[d][o]] = o; if(ns[ch[d][o]].r > ns[o].r) { int t = ch[d][o]; rotate(t); o = t; } maintain(o); return ans; } int pid[maxn], tot[maxn][maxn], n, m; void init() { sort(ps + 1, ps + cp + 1); for(int i = 1; i <= (cp >> 1); i++) swap(ps[i], ps[cp-i+1]); for(int i = 1; i <= cp; i++) if(ps[i].id <= n) pid[ps[i].id] = i; // for(int i = 1; i <= cp; i++) printf("point[%d]: %d %d\n", i, ps[i].p.x, ps[i].p.y); for(int i = 1; i <= cp; i++) { memset(fa, 0, sizeof(fa)); memset(ch, 0, sizeof(ch)); rt = ToT = 0; for(int j = i; j <= cp; j++) { tot[i][j] = insert(rt, ps[j], ps[i]); if(i != j) tot[j][i] = -tot[i][j]; // printf("%d %d: %d\n", i, j, tot[i][j]); } } return ; } int rps[maxn], get[maxn]; int main() { n = read(); m = read(); st = Vec(-10001, -10001); for(int i = 1; i <= n; i++) { int x = read(), y = read(); ps[i] = Point(Vec(x, y), 0, i); } for(int i = 1; i <= m; i++) { int x = read(), y = read(), v = read(); ps[i+n] = Point(Vec(x, y), v, i + n); } cp = n + m; init(); int q = read(); while(q--) { int t = read(); for(int i = 0; i < t; i++) rps[i] = pid[read()]; // for(int i = 0; i < t; i++) printf("%d%c", rps[i], i < t - 1 ? ‘ ‘ : ‘\n‘); int ans = 0; for(int i = 0; i < t; i++) ans += tot[rps[i]][rps[(i+1)%t]]; printf("%d\n", abs(ans)); } return 0; }
顺便完成预习“向量”的作业。。。
[BZOJ2391]Cirno的忧郁
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。