Crane POJ2991——线段树+几何

Crane POJ2991——线段树+几何

由于向量的可叠加性，这道题可以用线段树维护，配合一些几何的知识，代码还是挺好写的。

然而因为一个括号忘了去卡了好几个小时 ((٩(//̀Д/́/)۶)) ，果然应了那句话，改越久的BUG往往越ZZ

#include #include #include #include #include using namespace std;const int maxn = 1e4 + 10;const double PI = acos(-1.0);int n, c;struct Node { int angle; double x, y;}node[maxn<<2];int lazy[maxn<<2];void change(int root, int a) { double angle = a * PI / 180; double x = node[root].x, y = node[root].y; node[root].x = x * cos(angle) - y * sin(angle); node[root].y = y * cos(angle) + x * sin(angle); node[root].angle = (node[root].angle + a) % 360;}void pushup(int root) { node[root].x = node[root<<1].x + node[root<<1|1].x; node[root].y = node[root<<1].y + node[root<<1|1].y;}void pushdown(int root) { if (!lazy[root]) return; change(root<<1, lazy[root]); change(root<<1|1, lazy[root]); lazy[root<<1] += lazy[root]; lazy[root<<1|1] += lazy[root]; lazy[root] = 0;}void build(int l, int r, int root) { node[root].angle = 0; node[root].x = 0; node[root].y = 0; lazy[root] = 0; if (l == r) { scanf("%lf", &node[root].y); return; } int mid = (l + r)>>1; build(l, mid, root<<1); build(mid + 1, r, root<<1|1); pushup(root);}void update(int l, int r, int root, int ll, int rr, int val) { if (ll <= l && r <= rr) { change(root, val); lazy[root] += val; return; } pushdown(root); int mid = (l + r)>>1; if (ll <= mid) update(l, mid, root<<1, ll, rr, val); if (mid < rr) update(mid + 1, r, root<<1|1, ll, rr, val); pushup(root);}int query(int l, int r, int root, int pos) { if (l == r) return node[root].angle; int mid = (l + r)>>1; pushdown(root); if (pos <= mid) return query(l, mid, root<<1, pos); else return query(mid + 1, r, root<<1|1, pos);}int main() { int flag = 0; while (~scanf("%d %d", &n, &c)) { if (flag++) printf("\n"); build(1, n, 1); int s, a; while (c--) { scanf("%d %d", &s, &a); int angle = 180+a-query(1, n, 1, s+1)+query(1, n, 1, s); update(1, n, 1, s + 1, n, angle); printf("%.2lf %.2lf\n", node[1].x, node[1].y); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。