poj2991起重机题解《挑战程序设计竞赛》

地址

题解

本来以为这是⼀个简单的线段树模板 不料始终不太明⽩线段树如何记录转动⾓度后的各个线段端的XY值学习了⽹络上的⼀些博客题解 感觉似是⽽⾮ 谈到复数 ⾓度 向量等，有点不太好理解现在这⾥将⾃⼰的理解记录如下如图

1 预备知识

使⽤线段树记录的内容如下 指⽰某段线段的组合 以第⼀条线段为垂直 最后的线段的端点的X Y值

途中1~2 线段 和3~5线段 就是线段树节点1~5的⼦节点 那么线段树节点1~5 就记录1~5结合后的X Y 值以及两个⼦节点结合的⾓度值由于3~5线段的XY 是以⾃⼰的第⼀条线段为垂直起点为0 0 计算出来的X Y

那么在于1~2线段合并的时候 并不是简单的将两⼦节点的X Y相加即可得到1~5线段的XY ⽽是要加⼊旋转了相对⾓度 该⾓度由记录1~5线段的线段树节点记录1~2线段部分的X Y值 旋转相对⾓度的公式推导如下其实也就是

xNew = x * cosB - y * sinByNew = x * sinB + y * cosB

再来和 1~2线段的X Y相加即可得到1~5线段的X Y，并将该两⼦节点的相对⾓度记录在⽗节点中

预备知识讲完2 解答步骤如下

⼀ 建造线段树 build(1,1,n); 由于每条线段都是垂直连接 所以X 均为0 相对⾓度全部为0

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*2, rson=k*2+1; int m=(l+r)/2; build(lson,l,m); build(rson,m+1,r); y[k]=y[lson]+y[rson]; }}

⼆ 某段线段转动⾓度后

题意输⼊的⾓度是si和si+1逆时针⾓度⽽不是旋转的⾓度，⽽是需要转到的结果⾓度， 所以我们需要进⾏转换 。所以使⽤了pre数组记录每段线段与相邻线段的逆时针间隔⾓度，这样接收到题意输⼊⾓度a后

a-pre[s] 就是实际要转动的⾓度 ⽽且需要更新pre[s] 以便下次计算

change(s,ang-pre[s],1,1,n);

pre[s]=ang; // 要求改变为a度 考虑之前已改变过

chang()代码就是批量更新需要转换的⾓度和X Y

只有旋转的起点线段在当前线段树节点的左⼦节点 我们才更新当前线段树节点的⾓度记录如图

假设节点4 向3旋转90度那么合并1 2的时候⽆更新

合并3 4的时候 3~4节点的⾓度要在原来记录上再旋转90

合并1~2 3~4为1~4的时候⽆需更新⾓度 因为 3~4 已经旋转 与1 ~2的相对⾓度 并没有变化同样 5~8节点流程中⽆变化

但是合并1~4 5~8节点的时候 ⾓度需要旋转90

整个流程下来 4 5~8 ⾓度均旋转更新1次 符合题⽬的集合意义最后返回1~8节点记录的X Y即可 代码如下

1 #include 2 #include 3 #include 4 #include 5 using namespace std;

6 const double PI = acos(-1.0); 7 const int N = 10005; 8

9 int n, c, L[N];10 double pre[N];11

12 double angT[N << 2];

13 double x[N << 2], y[N << 2];14

15 void build(int k, int l, int r) {16 angT[k] = x[k] = 0.0;17 if (r == l) y[k] = L[l];18 else {

19 int lson = k * 2, rson = k * 2 + 1;20 int m = (l + r) / 2;21 build(lson, l, m);22 build(rson, m + 1, r);23 y[k] = y[lson] + y[rson];24 }25 }26 27

28 void change(int s, double ang, int k, int l, int r) {

29 if (s < l || l == r) return; // 操作位置不在范围内 或 区间长度为1 不作处理30 else if (s <= r) {

31 int lson = k * 2, rson = k * 2 + 1;32 int m = (l + r) / 2;

33 change(s, ang, lson, l, m);

34 change(s, ang, rson, m + 1, r); // 先处理左右⼦区间

35 if (s <= m) angT[k] += ang; // 操作位置位于区间的左⼦区间内 可根据左右⼦区间的向量更新36

37 double sina = sin(angT[k]), cosa = cos(angT[k]);38 x[k] = x[lson] + (x[rson] * cosa - y[rson] * sina);39 y[k] = y[lson] + (x[rson] * sina + y[rson] * cosa);40 }41 }42 43 44 /*

45 Sample Input46 47 2 148 10 549 1 9050 51 3 252 5 5 553 1 27054 2 90

55 Sample Output56

57 5.00 10.0058

59 -10.00 5.0060 -5.00 10.0061 */62

63 int main()64 {

65 while (~scanf(\"%d%d\", &n, &c)) {66 for (int i = 1; i <= n; i++) {67 scanf(\"%d\", &L[i]);68 pre[i] = PI;69 }

70 build(1, 1, n);71 while (c--) {

72 int s, a; scanf(\"%d%d\", &s, &a);73 double ang = (double)a / 180.0*PI;74 change(s, ang - pre[s], 1, 1, n);75 pre[s] = ang;

76 printf(\"%.2f %.2f\\n\", x[1], y[1]);77 }

78 printf(\"\\n\");79 }80

81 return 0;82 }

View Code