[Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)] - E Robot Arm

洛谷传送门

Codeforces传送门

题目大意

给你一个有$n$段的机械臂， 给出$m$个操作， 每次将一截机械臂伸长 l i l_i li​或顺时针旋转$l$°。 在每次操作后你需要回答一开始最靠右点当前的位置。

解题分析

很好的一道线段树题， 假设$[l-1,l]$是水平的， 维护$[l,r]$相对于$l$的位置和最右端机械臂的角度， 然后就可以用线段树合并区间得到答案。

总复杂度$O(Nlog(N))$。

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 300500
#define db double
#define ls (now << 1)
#define rs (now << 1 | 1)
#define ll long long
template <class T>
IN void in(T &x)
{x = 0; R char c = gc;for (; !isdigit(c); c = gc);for (;  isdigit(c); c = gc)x = (x << 1) + (x << 3) + c - 48;
}
int n, m;
template <class T> IN T sqr(T x) {return x * x;}
const db PI = std::acos(-1);
struct Node {db x, y, rig;} tree[MX << 2];
IN void pushup(R int now)
{db rlen = std::sqrt(sqr(tree[rs].x) + sqr(tree[rs].y));db rang = std::atan2(tree[rs].y, tree[rs].x);tree[now].x = tree[ls].x + rlen * std::cos(tree[ls].rig + rang);tree[now].y = tree[ls].y + rlen * std::sin(tree[ls].rig + rang);tree[now].rig = tree[ls].rig + tree[rs].rig;
}
void build(R int now, R int lef, R int rig)
{if (rig - lef == 1){tree[now].x = 1, tree[now].y = 0, tree[now].rig = 0;return;}int mid = lef + rig >> 1;build(ls, lef, mid), build(rs, mid, rig);pushup(now);
}
IN void modify(R int now, R int lef, R int rig, R db dang, R db dlen, R int tar)
{if (lef + 1 == rig){db len = std::sqrt(sqr(tree[now].x) + sqr(tree[now].y));db ang = std::atan2(tree[now].y, tree[now].x);len += dlen, ang += dang;tree[now].x = std::cos(ang) * len;tree[now].y = std::sin(ang) * len;tree[now].rig = ang;return;}int mid = lef + rig >> 1;if (tar <= mid) modify(ls, lef, mid, dang, dlen, tar);else modify(rs, mid, rig, dang, dlen, tar);pushup(now);
}
int main(void)
{int typ, pos, del;in(n), in(m); build(1, 0, n);W (m--){in(typ), in(pos), in(del);if (typ & 1) modify(1, 0, n, 0, del, pos);else modify(1, 0, n, -1.0 * del / 180 * PI, 0, pos);printf("%.10lf %.10lf\n", tree[1].x, tree[1].y);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！