本文共 3100 字，大约阅读时间需要 10 分钟。
题意：
例如s是线段AB,s+1是线段BC，那么就是要把角ABC置为a度（逆时针方向）。
把每条线段都看成一个向量，则最后的端点就是全部向量的和，每次更新就把[s+1，n]之间的向量旋转某个角度b。这个角度b可以由目前s的角度，s+1的角度，输入的a这三个量得到。向量的旋转则是左乘一个旋转矩阵就行了。
线段树结点维护两个信息
这个区间的向量和、旋转度数
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef pair pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}#define clr0(a) memset(a,0,sizeof(a))#define clr1(a) memset(a,-1,sizeof(a))void debug() {#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}char getch() { char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}double Cos[360],Sin[360]; // 据说能预处理能加速，大概快了200msstruct Vector { double x,y; Vector(double x,double y):x(x),y(y) {} Vector() {} Vector operator + (const Vector& a) { return Vector(x+a.x,y+a.y); }};Vector operator *(const int& ang, const Vector &v) { //向量的旋转变换 double x=Cos[ang]*v.x-Sin[ang]*v.y; double y=Sin[ang]*v.x+Cos[ang]*v.y; return Vector(x,y);}const int maxn=10010;const double EXP=10e-10; //以前发现有时会输出-0.000的情况，于是加上去了，不加也能ACVector v[maxn<<2]; int rota[maxn<<2];int PushUp(int idx) { v[idx]=v[idx<<1]+v[idx<<1|1]; rota[idx]=0; return 0;}int PushDown(int idx) { if(rota[idx]!=0) { rota[idx<<1]=(rota[idx<<1]+rota[idx])%360; rota[idx<<1|1]=(rota[idx<<1|1]+rota[idx])%360; v[idx<<1]=rota[idx]*v[idx<<1]; v[idx<<1|1]=rota[idx]*v[idx<<1|1]; rota[idx]=0; } return 0;}int build(int idx,int l,int r) { if(l==r) { double y; scanf("%lf",&y); v[idx]=Vector(0,y); rota[idx]=0; return 0; } int mid=(r+l)>>1; build(lson); build(rson); PushUp(idx); return 0;}int update(int idx,int l,int r,int tl,int tr,int ang) { if(tl<=l&&tr>=r) { rota[idx]=(rota[idx]+ang)%360; v[idx]=ang*v[idx]; return 0; } int mid=(r+l)>>1; PushDown(idx); if(tl<=mid)update(lson,tl,tr,ang); if(tr>mid)update(rson,tl,tr,ang); PushUp(idx); return 0;}int quary(int idx,int l,int r,int tl,int tr) { if(tl<=l&&tr>=r) { return rota[idx]; } PushDown(idx); int mid=(r+l)>>1; int x; if(tl<=mid)x=quary(lson,tl,tr); if(tr>mid)x=quary(rson,tl,tr); return x;}int main() { for(int i=0;i<360;i++) { Cos[i]=cos(i*PI/180.0); Sin[i]=sin(i*PI/180.0); } int n,c; int ca=1; while(scanf("%d%d",&n,&c)!=EOF) { if(ca!=1) printf("\n"); build(1,1,n); for(int i=1; i<=c; i++) { int x,ang; scanf("%d%d",&x,&ang); int q1=quary(1,1,n,x,x); int q2=quary(1,1,n,x+1,x+1); int a=(q1+270+ang-q2-90+360)%360; update(1,1,n,1+x,n,a); printf("%.2lf %.2lf\n",v[1].x+EXP,v[1].y+EXP); } ca++; } return 0;}
转载于:https://www.cnblogs.com/BMan/p/3263999.html
