簡(jiǎn)述題意:
一堆豎直依次排列，端點(diǎn)處連接起來(lái)。現(xiàn)在給出這樣一種操作，將第i個(gè)桿子和第i+1個(gè)桿子直接的角度調(diào)整為180+degree,當(dāng)然，i+1個(gè)桿子以后的桿子連著它一起轉(zhuǎn)動(dòng)。求最后一個(gè)桿子的坐標(biāo)
可以這樣設(shè)置線段樹(shù)的域
1 struct
2 {
3 int s,e;
4 double x,y;
5 int turn;
6 }st[N];
turn代表當(dāng)前線段
整體旋轉(zhuǎn)過(guò)的角度
維護(hù)策略可以這樣寫(xiě)：用到了坐標(biāo)的旋轉(zhuǎn)變換矩陣:
|cosx -sinx |
|sinx cosx|
1 inline void change(double &x,double &y,double turn)
2 {
3 double tx=x,ty=y;
4 x=cos(turn)*tx-sin(turn)*ty;
5 y=sin(turn)*tx+cos(turn)*ty;
6 }
7 inline void update(int pos,int add)
8 {
9 st[pos].turn=(st[pos].turn+add)%360;
10 change(st[pos].x,st[pos].y,degree(add%360));
11 }
其他標(biāo)記下移什么的和普通線段樹(shù)一樣，就不贅述了，貼代碼
1
# include <cstdio>
2# include <cmath>
3using namespace std;
4const int N=50000;
5const double eps=1e-6;
6# define degree(a) ((a)/180.0*3.141592653)
7struct
8
{
9
int s,e;
10 double x,y;
11 int turn;
12
}st[N];
13int len[N];
14inline void change(double &x,double &y,double turn)
15{
16 double tx=x,ty=y;
17 x=cos(turn)*tx-sin(turn)*ty;
18 y=sin(turn)*tx+cos(turn)*ty;
19}
20inline void update(int pos,int add)
21{
22 st[pos].turn=(st[pos].turn+add)%360;
23 change(st[pos].x,st[pos].y,degree(add%360));
24}
25void init(int s,int e,int pos=1)
26{
27 st[pos].s=s;
28 st[pos].e=e;
29 st[pos].turn=0;
30 if(e==s+1)
31 st[pos].y=len[s],st[pos].x=0;
32 else
33
{
34 init(s,(s+e)>>1,pos<<1);
35 init((s+e)>>1,e,(pos<<1)+1);
36 st[pos].y=st[pos<<1].y+st[(pos<<1)+1].y;
37 st[pos].x=0;
38
}
39}
40int get(int target,int pos=1)
41{
42 if(st[pos].e==st[pos].s+1) return st[pos].turn;
43 else if(target<((st[pos].s+st[pos].e)>>1)) return st[pos].turn+get(target,pos<<1);
44 else return st[pos].turn+get(target,(pos<<1)+1);
45}
46
47void insert(int s,int e,int add,int pos=1)
48{
49 if(s==st[pos].s&&e==st[pos].e)
50 update(pos,add);
51 else
52 {
53 if(st[pos].turn)
54 {
55 update(pos<<1,st[pos].turn);
56 update((pos<<1)+1,st[pos].turn);
57 st[pos].turn=0;
58 }
59 if(e<=(st[pos].s+st[pos].e)>>1)
60 insert(s,e,add,pos<<1);
61 else if(s>=(st[pos].s+st[pos].e)>>1)
62 insert(s,e,add,(pos<<1)+1);
63 else
64 {
65 insert(s,(st[pos].s+st[pos].e)>>1,add,pos<<1);
66 insert((st[pos].s+st[pos].e)>>1,e,add,(pos<<1)+1);
67 }
68 st[pos].x=st[pos<<1].x+st[(pos<<1)+1].x;
69 st[pos].y=st[pos<<1].y+st[(pos<<1)+1].y;
70 }
71}
72int main()
73{
74 int n,c,pos,turn,d1,d2;
75 while(scanf("%d%d",&n,&c)!=EOF)
76 {
77 for(int i=1;i<=n;i++)
78 scanf("%d",len+i);
79 init(1,n+1);
80 while(c--)
81 {
82 scanf("%d%d",&pos,&turn);
83 d1=get(pos++);
84 d2=get(pos);
85 insert(pos,n+1,turn-180-d2+d1);
86 printf("%.2f %.2f\n",st[1].x+eps,st[1].y+eps);
87 }
88 }
89 return 0;
90}