题目大意:

给定n条首尾相接的线段的长度

第一条从0,0开始,所有线段垂直与x轴向上延伸

给定c次操作 每次操作给定 s,a

使得 由第s条线段的角度 逆时针旋转a后 达到第s+1条线段的角度

每次操作后输出最后一条线段末尾端点的坐标

向量逆时针旋转公式为

x' = x * cos(A) - y * sin(A); y' = x * sin(A) + y * cos(A);

一个向量  (x,y)  可分解两个向量为 垂直于y轴的(x,0) 和垂直于x轴的 (0,y)

两个分向量逆时针A度后

(x',0) = ( x*coa(A),x*sin(A) )   (0,y') = ( -y*sin(A),y*cos(A) )

两个旋转后的分向量 再合并就可得到旋转后的 (x',y')

用线段树维护一段区间内由 该区间内第一段线段的起点 指向 最后一段线段的末尾的向量

每次操作更新区间时 我们只对 操作位置处于当前区间的左子区间 的区间更新

那么这样当更新一段区间时 当前向量=左子区间的向量+右子区间旋转后的的向量

并且对于区间长度为1的区间不做处理

#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
const int N=; int n,c,L[N];
double pre[N]; double angT[N<<];
double x[N<<],y[N<<]; void build(int k,int l,int r) {
angT[k]=x[k]=0.0;
if(r==l) y[k]=L[l];
else {
int lson=k*, rson=k*+;
int m=(l+r)/;
build(lson,l,m);
build(rson,m+,r);
y[k]=y[lson]+y[rson];
}
}
void change(int s,double ang,int k,int l,int r) {
if(s<l || l==r) return; // 操作位置不在范围内 或 区间长度为1 不作处理
else if(s<=r) {
int lson=k*, rson=k*+;
int m=(l+r)/;
change(s,ang,lson,l,m);
change(s,ang,rson,m+,r); // 先处理左右子区间
if(s<=m) angT[k]+=ang; // 操作位置位于区间的左子区间内 可根据左右子区间的向量更新 double sina=sin(angT[k]), cosa=cos(angT[k]);
x[k]=x[lson]+(x[rson]*cosa-y[rson]*sina);
y[k]=y[lson]+(x[rson]*sina+y[rson]*cosa);
}
} int main()
{
while(~scanf("%d%d",&n,&c)) {
for(int i=;i<=n;i++) {
scanf("%d",&L[i]);
pre[i]=PI;
}
build(,,n);
while(c--) {
int s,a; scanf("%d%d",&s,&a);
double ang=(double)a/180.0*PI;
change(s,ang-pre[s],,,n);
pre[s]=ang; // 要求改变为a度 考虑之前已改变过
printf("%.2f %.2f\n",x[],y[]);
}
printf("\n");
} return ;
}

最新文章

  1. hadoop2.2.0伪分布式搭建3--安装Hadoop
  2. Mongodb Manual阅读笔记:CH9 Sharding
  3. soapui中文操作手册(五)----入门与安全测试
  4. ADF_Starting系列8_使用EJB/JPA/JSF通过ADF构建Web应用程序之扩展UI Method
  5. C/C++内存泄漏及检测 转
  6. HDFS副本机制&amp;负载均衡&amp;机架感知&amp;访问方式&amp;健壮性&amp;删除恢复机制&amp;HDFS缺点
  7. vs-ps combination error
  8. Zend studio注册码
  9. nginx 调优
  10. File类的使用
  11. 分享几个实用的jquery工具函数
  12. Java自定义简单标签
  13. 一个完整的Installshield安装程序实例—艾泽拉斯之海洋女神出品(四) --高级设置二
  14. WIN7远程桌面重启、关机
  15. leetcode第24题--Reverse Nodes in k-Group
  16. 遇到的面试题-sql
  17. Ansible小记
  18. json与csv的基础用与法
  19. 48 【golang】json的效率
  20. 没有安装hiredis

热门文章

  1. android studio import cannot resolve symbol错误
  2. python re模块使用
  3. myeclipse 启动卡住的解决办法
  4. 【转】java使用java.lang.management监视和管理 Java 虚拟机
  5. Perl 换行打印
  6. git入门基本命令
  7. html5本地存储(一)------ web Storage
  8. rmq +二分暴力 hdu 5726
  9. 不走弯路,微信小程序的快速入门?
  10. PHP之数据连接方法(二)