| ||||||||||
| 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