这个题比较神奇。大意就是有一个长杆,杆上有一些关节点,可以转动,然后每次操作就是将某个关节点的角度变成某个角度,最后求末尾的坐标。
线段树每个结点存的信息是,这一段末尾的x坐标,y坐标,以及该段与y轴的夹角,其中x,y坐标是与上一段线段的相对坐标。这样的好处是显而易见的。注意,这个与y轴的夹角是该段线段顺时针旋转至初始状态的角度,如下图
然后每次更新的时候需要注意,是把某个结点后的所有线段都旋转
/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 1000000000
#define L(x) x<<1
#define R(x) x<<1|1
#define PI acos(-1.0)
#define eps 1e-7
using namespace std;
int len[MAXN];
struct node
{
int left, right, mid;
double x, y;
int turn;
}tree[4 * MAXN];
void up(int C)
{
tree[C].y = tree[L(C)].y + tree[R(C)].y;
tree[C].x = tree[L(C)].x + tree[R(C)].x;
}
void change(int C, int turn)
{
tree[C].turn = (tree[C].turn + turn) % 360;
double tx = tree[C].x;
double ty = tree[C].y;
double degree = turn * 1.0 / 180.0 * PI;
tree[C].x = tx * cos(degree) - ty * sin(degree);
tree[C].y = tx * sin(degree) + ty * cos(degree);
}
void down(int C)
{
if(tree[C].turn)
{
change(L(C), tree[C].turn);
change(R(C), tree[C].turn);
tree[C].turn = 0;
}
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) >> 1;
tree[C].x = 0;
tree[C].turn = 0;
if(s == e) {tree[C].y = len[s]; return;}
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
up(C);
}
int query(int C, int p)
{
if(tree[C].left == tree[C].right)
return tree[C].turn;
down(C);
if(tree[C].mid >= p) return query(L(C), p);
else return query(R(C), p);
}
void update(int s, int e, int turn, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
change(C, turn);
return;
}
down(C);
if(tree[C].mid >= s) update(s, e, turn, L(C));
if(tree[C].mid < e) update(s, e, turn, R(C));
up(C);
}
int main()
{
int n, c;
int x, y;
bool fg = 0;
while(scanf("%d%d", &n, &c) != EOF)
{
if(fg) puts("");
fg = 1;
for(int i = 1; i <= n; i++)
scanf("%d", &len[i]);
make_tree(1, n, 1);
for(int i = 1; i <= c; i++)
{
scanf("%d%d", &x, &y);
int pos1 = query(1, x);
int pos2 = query(1, x + 1);
int t = (-180 + pos1 - pos2 + y + 360) % 360;
update(x + 1, n, t, 1);
printf("%.2f %.2f\n", tree[1].x + eps, tree[1].y + eps);
}
}
return 0;
}
分享到:
相关推荐
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ3468,线段树处理,注意longlongint
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
NULL 博文链接:https://128kj.iteye.com/blog/1705139