Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴份c++代码#include <iostream> #include <math.h> using namespace std; const double Pi_D180 = acos(-1.0) / 180.0;// Pi除以180 struct Point { double x;//水平分量 double y;//竖直分量 int a;//夹角 }; double pss[361], psc[361];//打表记录三角函数值 Point p[40005];//线段树的节点 int prea[40005];//用来记录每个第 i 个与第 i + 1 条线段之间的角度 int main() { int n, c, s, a, pSize, me, fa, delta;//线段数 操作数 角度 线段树大小 当前节点 父节点 角度变化量 for (int i = 0; i < 361; i++)//打表记录三角函数值 { pss[i] = sin(i * Pi_D180); psc[i] = cos(i * Pi_D180); } while (cin >> n >> c) { for (int i = 0; i < 40005; i++)//将树初始化为 0 { p[i].a = 0; p[i].x = 0; p[i].y = 0; prea[i] = 0; } pSize = 1; while (pSize < n)//确定树所需的大小 { pSize <<= 1; } pSize--;//此时 aSize 为树最后一层的行首节点的下标(线段树最后一层的每个节点只维护一条线段) for (int i = 0; i < n; i++)//将线段长度输入到线段树最后一层,若树不满则视作用长度为 0 的线段填满 { cin >> p[i + pSize].y; } for (int i = pSize >> 1; i; i >>= 1)//向上初始化线段树的节点 { for (int j = 0; j <= i; j++) { p[i + j].y = p[2 * (i + j) + 1].y + p[2 * (i + j) + 2].y; } } p[0].y = p[1].y + p[2].y; for (int i = 0; i < c; i++) { cin >> s >> a; delta = (900 - a - prea[s]) % 360;//根据 a 和 prea 推出角度变化量 prea[s] = 540 - a;//记录此次修改后的第 s 条与第 s + 1 条线段的夹角 me = pSize + s - 1;//先将当前节点设在最后一层 while (!(s & true))//找到线段树中维护此角度的节点 { me = (me - 1) >> 1; s >>= 1; } fa = (me - 1) >> 1;//此时 p[fa] 是维护第 s 条与第 s + 1 线段的夹角的节点 while (me)//向上更新节点 { fa = (me - 1) >> 1; if (me & true)//如果 me 为左子节点 { p[fa].a = (p[fa].a + delta) % 360; p[fa].x = p[me].x + p[me + 1].x * psc[p[fa].a] + p[me + 1].y * pss[p[fa].a]; p[fa].y = p[me].y + p[me + 1].y * psc[p[fa].a] - p[me + 1].x * pss[p[fa].a]; } else//如果 me 为右子节点 { p[fa].x = p[me - 1].x + p[me].x * psc[p[fa].a] + p[me].y * pss[p[fa].a]; p[fa].y = p[me - 1].y + p[me].y * psc[p[fa].a] - p[me].x * pss[p[fa].a]; } me = fa; } printf_s("%.2f %.2f\n", p[0].x, p[0].y); } cout << '\n'; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator