您當前位置：首頁 > 互聯網 > poj 2991 Crane(線段樹)

poj 2991 Crane(線段樹)

來源：程序員人生發布時間：2014-10-10 08:00:01 閱讀次數：2929次

題目鏈接：poj 2991 Crane

題目大意：就是有一個機械手臂，有n結，給定每節的長度，一開始為垂直的。有m次操作，每次將x關節變成角度d，并且輸出手臂末端的坐標。

解題思路：點的旋轉公式(r為逆時針的角度):

x′=x?cos(r)?y?sin(r)
y′=x?sin(r)+y?cos(r)

沒有做過類似的題目，線段樹每個節點記錄的為每節旋轉的角度以及單節末端的位置。每次旋轉新的角度，需要根據前一個節點的角度和當前節點的角度來計算（因為它不是再旋轉d，而是變成角度d

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const double pi = atan(1.0) * 4;

#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
const int maxn = 10005;

int lc[maxn * 4], rc[maxn * 4], s[maxn * 4], v[maxn * 4];
double xi[maxn * 4], yi[maxn * 4];

void rotate (int u, int deg) {
    double r = deg * pi / 180;
    double x = xi[u] * cos(r) - yi[u] * sin(r);
    double y = xi[u] * sin(r) + yi[u] * cos(r);

    xi[u] = x; yi[u] = y;
    s[u] = (s[u] + deg) % 360;
    v[u] = (v[u] + deg) % 360;
}

void pushup (int u) {
    xi[u] = xi[lson(u)] + xi[rson(u)];
    yi[u] = yi[lson(u)] + yi[rson(u)];
}

void pushdown (int u) {
    if (s[u]) {
        rotate(lson(u), s[u]);
        rotate(rson(u), s[u]);
        s[u] = 0;
    }
}

void build (int u, int l, int r) {
    lc[u] = l;
    rc[u] = r;
    s[u] = v[u] = 0;

    if (l == r) {
        xi[u] = 0;
        scanf("%lf", &yi[u]);
        return ;
    }

    int mid = (l + r) / 2;
    build (lson(u), l, mid);
    build (rson(u), mid + 1, r);
    pushup(u);
}

int query (int u, int pos) {
    if (lc[u] == rc[u])
        return v[u];

    pushdown(u);
    int mid = (lc[u] + rc[u]) / 2;
    if (pos <= mid)
        return query(lson(u), pos);
    else
        return query(rson(u), pos);
    pushup(u);
}

void modify (int u, int l, int r, int deg) {
    if (l <= lc[u] && rc[u] <= r) {
        rotate(u, deg);
        return;
    }

    pushdown(u);
    int mid = (lc[u] + rc[u]) / 2;
    if (l <= mid)
        modify(lson(u), l, r, deg);
    if (r > mid)
        modify(rson(u), l, r, deg);
    pushup(u);
}

int N, M;

int main () {
    int cas = 0, d, r;
    while (scanf("%d%d", &N, &M) == 2) {
        if (cas++)
            printf("
");
        build (1, 0, N-1);

        while (M--) {
            scanf("%d%d", &d, &r);
            r = (query(1, d - 1) + 180 + r - query(1, d)) % 360;
            modify(1, d, N - 1, r);
            printf("%.2lf %.2lf
", xi[1], yi[1]);
        }
    }
    return 0;
}

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 Linux內核源碼學習之僵尸進程

下一篇 Android時鐘應用的定時框架分析

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

poj 2991 Crane(線段樹)