POJ2991 Crane(线段树成段更新+向量旋转)

16-10-18 来源：[db:作者]

收藏我要投稿

这道题呢，涉及的是线段树的成段更新，这里我们更新的每一段的坐标，由于我们求的是最后一段顶点的坐标，所以我们只需要把所有段的顶点的坐标加起来就是最终的答案。

我们这里用的是向量，那么来了，向量的旋转坐标是怎么变化的呢，这里涉及的是一些数学知识，看下图。

这里写图片描述

所以呢，向量的坐标变化为:
Vx=cosA*x-sinA*y
Vy=cosA*y+sinA*x

接下来就是手写线段树了，就加了一个懒惰标记，成段跟新[q+1,Ｎ]这一大段中所有小段的坐标，
q+1,q+2,...,N.由于我们求的是最后一段的点的坐标，所以我们只需要把[1,N]每一段的坐标
加起来就可以了(可能这里会疑问，怎么可以全部加起来呢，那一定坐标变大了，其实，前面说过，
我们更新的每一段的坐标，这些坐标都对应某一段的起点(0,0)，旋转后的坐标也是相对的，有正
有负，所以，最后加起来，一定是最顶点的左边，即sum[1]).大概就这些。
ps:这里给的角度是改变后所处的角度，所以我们还需要算出旋转之后的角度。(英语好真的很重要，题都读不懂gg)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MOD 1000000007
#define fir first
#define sec second
#define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin)
#define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout)
#define mes(x, m) memset(x, m, sizeof(x))
#define Pii pair
#define Pll pair
#define INF 1e9+7
#define Pi 4.0*atan(1.0)
#define lowbit(x) (x&(-x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-12;
const int maxn = 10010;
using namespace std;
inline int read(){
    int x(0),op(1);
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')op=-1,ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*op;
}

//Xi=cosx-siny
//Yi=sinx+cosy

double sum[maxn<<2];　//坐标
double re[maxn<<2];　//懒惰标记
double pre[maxn];　//各段当前的角度
double x[maxn<<2];　
double y[maxn<<2];
double Change(double ang)　//角度转弧度
{
    double res=ang/180*Pi;
    return res;
}
inline void work(double ang,int rt)　
{
    if(ang>=360){　　//控制在360以内，其实也可以不用
        ang=(int)ang%360;
    }
    double res=Change(ang);
    double vx=x[rt];
    double vy=y[rt];
    x[rt]=cos(res)*vx-sin(res)*vy;　//向量旋转的坐标变化
    y[rt]=cos(res)*vy+sin(res)*vx;  //
}
inline void PushUp(int rt)
{
    x[rt]=x[rt<<1]+x[rt<<1|1];
    y[rt]=y[rt<<1]+y[rt<<1|1];
}
inline void PushDown(int rt)
{
    if(re[rt]){
        work(re[rt],rt<<1);
        work(re[rt],rt<<1|1);
        re[rt<<1]+=re[rt];
        re[rt<<1|1]+=re[rt];
        re[rt]=0;
    }
}
inline void buildTree(int l,int r,int rt)
{
    re[rt]=0,x[rt]=0;　//初始化
    if(l==r){
        scanf("%lf",&y[rt]);
        return;
    }
    int m=(l+r)>>1;
    buildTree(lson);
    buildTree(rson);
    PushUp(rt);
}
inline void update(double ang,int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R){
        re[rt]+=ang;
        work(ang,rt);　
        return;
    }
    PushDown(rt);
    int m=(l+r)>>1;
    if(L<=m){
        update(ang,L,R,lson);
    }
    if(R>m){
        update(ang,L,R,rson);
    }
    PushUp(rt);
}
int main()
{
    //fin;
    int N,C;
    double ang,tmp;
    int lenCount;
    bool flag=false;
    while(~scanf("%d%d",&N,&C)){
        if(flag){
            cout<

点击复制链接与好友分享!回本站首页