其实今天没有什么好说的， 四个半小时全在做第一题
前两个小时在推式子， 但其中一个半小时的式子是没用的。
这时候突然知道正解怎么做了， 发现是道水题， 就花了一个半小时将代码打完了， 结果过不了小样例， 又花了一个小时， 但结束了都没调出来。
下来一看， 整场比赛有两道题可做， 而且两道的思路都很简单， 但T1非常难实现。
所以每道题看完题了以后还是要稍微想一想， 如果有大概方向的话甚至可以多想想， 不过一定不能想太久， 稍微想一想， 如果不是完全想出正解的话一定要再去康康其它的题目。
记录一下技巧：
平面上的位移可以考虑相对运动。
如果问题可以转化为矩阵的乘法， 那么一定要注意逆矩阵抵消贡献的技巧（具体看代码， 虽然我的做法不太是矩阵， 但异曲同工）：

题目

动点（point）

时间限制：3s

空间限制：512MiB

题目背景

本来准备放一道数值算法题，可惜这里位置太小…

题目描述

我们定义两类用于移动平面上一点 \(P\) 的指令 \(\lang\cdot\rang\) 和 \([\cdot]\)：

1. \(\lang p,q,t \rang\) 表示将 \(P\) 绕点 \((p,q)\) 逆时针旋转 \(\frac{t}{1800}\) 倍平角（即弧度制的 \(\frac{t\pi}{1800}\) 或角度制的 \(t\times 0.1^\circ\)）；
2. \([a,b,c]\) 表示将 \(P\) 移动到直线 \(ax+by+c=0\) 上与 \(P\) 距离最小的点（这里保证 \(a,b\) 不全为零）。

现在给出一个长为 \(n\) 的指令序列 \(g\)，现在你需要完成以下几种操作：

• 1 l r u v 表示对于下标在 \([l,r]\) 中的指令，将所有一类指令里的点 \((p,q)\)、二类指令里的直线 \(ax+by+c=0\) 沿着向量 \((u,v)\) 平移；
• 2 l r u v w 表示对于下标在 \([l,r]\) 中的指令，将所有一类指令里的点 \((p,q)\)、二类指令里的直线 \(ax+by+c=0\) 沿着直线 \(ux+vy+w=0\) 翻折（这里保证 \(u,v\) 不全为零）；
• 3 l r x y 表示对点 \(P=(x,y)\) 从左到右依次执行 \(g_l,g_{l+1},\dots,g_r\)，询问最终 \(P\) 被移动到了哪里。

输入格式

第一行两个正整数 \(n,m\)（\(1 \le n,m \le 10^5\)），\(n\) 表示指令序列的长度，\(m\) 表示操作次数。

接下来 \(n\) 行，每行四个整数：1 p q t 表示指令 \(\lang p,q,t \rang\)，2 a b c 表示指令 \([a,b,c]\)。

接下来 \(m\) 行，每行若干整数，表示一个操作，形式如题面所述。

输出格式

输出若干行，每行两个浮点数，表示每次询问最终点的坐标 。当你的答案与标准答案的相对或绝对误差小于 \(\epsilon=10^{-5}\) 时认为你的答案正确。

样例

样例输入 #1

3 6
2 1 1 1
1 2 2 900
2 2 -1 0
3 1 1 -1 -1
3 1 3 -1 -1
1 1 2 1 1
3 1 2 -1 -1
2 3 3 1 -1 0
3 2 3 -1 -1

样例输出 #1

-0.5 -0.5
0.7 1.4
5.5 0.5
5.2 2.6

样例解释 #1

输入文件第 6 行中，询问点 \((-1,-1)\) 依次执行 \(g_1,g_2,g_3\) 后得到的点。在执行 \(g_1\) 后点位于 \((-0.5,-0.5)\)，执行 \(g_2\) 后位于 \((4.5,-0.5)\)，执行 \(g_3\) 后位于 \((0.7,1.4)\)，故输出文件第二行为 0.7 1.4；

输入文件第 7 行中，将 \(g_1\) 变为了 \([1,1,-1]\)，将 \(g_2\) 变为了 \(\lang 3,3,900\rang\)；

输入文件第 9 行中，将 \(g_3\) 变为了 \([1,-2,0]\)。

测试点约束

本题共 \(25\) 个测试点，每个测试点 \(4\) 分。约束如下：

特殊性质 A：保证没有一类指令。

特殊性质 B：保证没有一类操作。

特殊性质 C：保证没有二类操作。

保证 \(1 \le l \le r \le n\)，保证所有输入均为绝对值不超过 \(10^9\) 的整数。

官方题解

题解 - 山路动点（point）

首先不管修改操作，只考虑询问。不难想到用矩阵处理：

• 沿着向量 \(v\) 平移：\(x \leftarrow x+v_x\)，\(y \leftarrow y+v_y\)
• 逆时针旋转 \(\theta\)：\(x \leftarrow x\cos \theta -y \sin \theta\)，\(y \leftarrow y \cos \theta + x \sin \theta\)
• 投影到方向 \(v\) 上：点乘 \(v\) 后数乘 \(v\)，再数乘一个 \(\frac{1}{|v|^2}\)

以上都可以表示为向量 \((x,y,1)\) 左乘矩阵，而两类指令都可以表示为上面的过程的组合。因此考虑线段树维护矩阵乘积。

再考虑如何把操作加入。一个基本的思想是，操作时我们不显式地更改指令，而是尝试更改坐标系。对于平移操作，我们完全可以先将点\(P\) 沿着逆方向平移，完成指令后再沿着正方向平移回来。写成矩阵形式就是把原来的指令矩阵 \(M\) 变成 \(DMD^{-1}\)，其中 \(D\) 为沿着向量 \((u,v)\) 平移对应的矩阵。这个很容易往线段树上打个乘法标记维护。对于翻折操作也是差不多的，我们可以尝试先把点翻过去，执行完指令再翻回来。需要注意的是在点翻到镜像位置之后，原有的旋转操作就需要把逆时针转变成顺时针转了。不过这还是很好办，我们对旋转维护 \(M,M'\) 分别表示逆时针、顺时针转对应的矩阵即可。那么翻折操作就是把 \(M\) 变为 \(RM'R\)，把 \(M'\) 变为 \(RMR\)，其中 \(R\) 是翻折对应的矩阵。

这题没怎么卡精度，应该不需要 long double 就能过。

代码

// ubsan: undefined
// accoders
/*
(x, y) (p, q)
(x - p, y - q)
l = sqrt((x - p)^2 + (y - q)^2)
(l * cos(A + B), l * sin(A + B))
(l * (cos(A) * cos(B) - sin(A) * sin(B)), l * (sin(A) * cos(B) + sin(B) * cos(A)))
((x - p) * cos(B) - (y - q) * sin(B), (y - q) * cos(B) + (x - p) * sin(B))
(x * cos(B) - y * sin(B) + (1 - cos(B)) * p + q * sin(B), x * sin(B) + y * cos(B) - p * sin(B) + q* (1 -
cos(B)))


(m, n) ax + by + c = 0
-bx + ay + z = 0
z = bx - ay
z = bm - an
-bx + ay + (bm - an) = 0

xby + ((a^2) / b)y + (bm - an) * (a / b) + c = 0
((a^2 + b^2) / b)y + am - (a^2 / b) * n + c = 0
y = ((a^2)n - abm - bc) / (a^2 + b^2)

ax + (b^2 / a)x - (bm - an) * (b / a) + c = 0
((a^2 + b^2) / a)x - (b^2 / a)m + bn + c = 0
x = (-abn + (b^2)m - ac) / (a^2 + b^2)


x = (-uvn + (v^2)m - uw) / (u^2 + v^2)
y = ((u^2)n - uvm - vw) / (u^2 + v^2)

2x - m = (-2uvn + ((v^2) - (u^2))m - 2uw) / (u^2 + v^2)
2y - n = (((u^2) - (v^2))n - 2uvm - 2vw) / (u^2 + v^2)
*/

#include <cstdio>
#include <algorithm>
#include <random>
#include <cmath>
using namespace std;

#define MAXN 100000
#define PI 3.14159265358979328346264

struct polynomial {
    double a = 0, b = 0, c = 0;

    polynomial() {}
    polynomial(double A, double B, double C) {
        a = A;
        b = B;
        c = C;
    }
};
mt19937 r(20061206);
struct fhq {
    int son[2];
    bool lazy = 0;
    pair<polynomial, polynomial> v[2], sum[2], lazy1, lazy2;
    int num = 0;
    int key = r();
} s[MAXN + 5];
int rt;
int tot = 0;

int newfhq(pair<polynomial, polynomial> v1, pair<polynomial, polynomial> v2) {
    ++tot;
    s[tot].son[0] = s[tot].son[1] = 0;
    s[tot].v[0] = s[tot].sum[0] = v1;
    s[tot].v[1] = s[tot].sum[1] = v2;
    s[tot].lazy = 0;
    s[tot].lazy1 = make_pair(polynomial(1, 0, 0), polynomial(0, 1, 0));
    s[tot].lazy2 = make_pair(polynomial(1, 0, 0), polynomial(0, 1, 0));
    s[tot].num = 1;

    return tot;
}
pair<polynomial, polynomial> operator*(pair<polynomial, polynomial> a, pair<polynomial, polynomial> b) {
    pair<polynomial, polynomial> c;

    c.first.a = a.first.a * b.first.a + a.second.a * b.first.b;
    c.first.b = a.first.b * b.first.a + a.second.b * b.first.b;
    c.first.c = a.first.c * b.first.a + a.second.c * b.first.b + b.first.c;
    c.second.a = a.first.a * b.second.a + a.second.a * b.second.b;
    c.second.b = a.first.b * b.second.a + a.second.b * b.second.b;
    c.second.c = a.first.c * b.second.a + a.second.c * b.second.b + b.second.c;

    return c;
}

void download(int p) {
    if (!p) {
        return;
    }
    if (s[p].son[0]) {
        s[s[p].son[0]].sum[0] = s[p].lazy1 * s[s[p].son[0]].sum[0] * s[p].lazy2;
        s[s[p].son[0]].v[0] = s[p].lazy1 * s[s[p].son[0]].v[0] * s[p].lazy2;
        s[s[p].son[0]].sum[1] = s[p].lazy1 * s[s[p].son[0]].sum[1] * s[p].lazy2;
        s[s[p].son[0]].v[1] = s[p].lazy1 * s[s[p].son[0]].v[1] * s[p].lazy2;
        s[s[p].son[0]].lazy1 = s[p].lazy1 * s[s[p].son[0]].lazy1;
        s[s[p].son[0]].lazy2 = s[s[p].son[0]].lazy2 * s[p].lazy2;
        if (s[p].lazy) {
            swap(s[s[p].son[0]].sum[0], s[s[p].son[0]].sum[1]);
            swap(s[s[p].son[0]].v[0], s[s[p].son[0]].v[1]);
            s[s[p].son[0]].lazy ^= 1;
        }
    }
    if (s[p].son[1]) {
        s[s[p].son[1]].sum[0] = s[p].lazy1 * s[s[p].son[1]].sum[0] * s[p].lazy2;
        s[s[p].son[1]].v[0] = s[p].lazy1 * s[s[p].son[1]].v[0] * s[p].lazy2;
        s[s[p].son[1]].sum[1] = s[p].lazy1 * s[s[p].son[1]].sum[1] * s[p].lazy2;
        s[s[p].son[1]].v[1] = s[p].lazy1 * s[s[p].son[1]].v[1] * s[p].lazy2;
        s[s[p].son[1]].lazy1 = s[p].lazy1 * s[s[p].son[1]].lazy1;
        s[s[p].son[1]].lazy2 = s[s[p].son[1]].lazy2 * s[p].lazy2;
        if (s[p].lazy) {
            swap(s[s[p].son[1]].sum[0], s[s[p].son[1]].sum[1]);
            swap(s[s[p].son[1]].v[0], s[s[p].son[1]].v[1]);
            s[s[p].son[1]].lazy ^= 1;
        }
    }
    s[p].lazy1 = make_pair(polynomial(1, 0, 0), polynomial(0, 1, 0));
    s[p].lazy2 = make_pair(polynomial(1, 0, 0), polynomial(0, 1, 0));
    s[p].lazy = 0;
}
void upload(int p) {
    s[p].num = s[s[p].son[0]].num + 1 + s[s[p].son[1]].num;
    if (s[p].son[0]) {
        s[p].sum[0] = s[s[p].son[0]].sum[0] * s[p].v[0];
        s[p].sum[1] = s[s[p].son[0]].sum[1] * s[p].v[1];
    } else {
        s[p].sum[0] = s[p].v[0];
        s[p].sum[1] = s[p].v[1];
    }
    if (s[p].son[1]) {
        s[p].sum[0] = s[p].sum[0] * s[s[p].son[1]].sum[0];
        s[p].sum[1] = s[p].sum[1] * s[s[p].son[1]].sum[1];
    }
}

void split(int p, int &l, int &r, int loc) {
    if (!p) {
        l = r = 0;

        return;
    }
    download(p);
    if (s[s[p].son[0]].num + 1 < loc) {
        l = p;
        split(s[p].son[1], s[l].son[1], r, loc - (s[s[p].son[0]].num + 1));
        upload(l);
    } else {
        r = p;
        split(s[p].son[0], l, s[r].son[0], loc);
        upload(r);
    }
}
int merge(int l, int r) {
    if (l == 0 || r == 0) {
        return l + r;
    }
    if (s[l].key > s[r].key) {
        download(l);
        s[l].son[1] = merge(s[l].son[1], r);
        upload(l);

        return l;
    } else {
        download(r);
        s[r].son[0] = merge(l, s[r].son[0]);
        upload(r);

        return r;
    }
}

void insert(pair<polynomial, polynomial> v1, pair<polynomial, polynomial> v2, int loc) {
    int h, t;

    split(rt, h, t, loc);
    rt = merge(h, merge(newfhq(v1, v2), t));
}
void change(int l, int r, pair<polynomial, polynomial> v1, pair<polynomial, polynomial> v2, bool flag) {
    int h, mid, t;

    split(rt, h, t, r + 1);
    split(h, h, mid, l);
    s[mid].lazy1 = v1 * s[mid].lazy1;
    s[mid].lazy2 = s[mid].lazy2 * v2;
    s[mid].sum[0] = v1 * s[mid].sum[0] * v2;
    s[mid].v[0] = v1 * s[mid].v[0] * v2;
    s[mid].sum[1] = v1 * s[mid].sum[1] * v2;
    s[mid].v[1] = v1 * s[mid].v[1] * v2;
    if (flag) {
        s[mid].lazy ^= 1;
        swap(s[mid].v[0], s[mid].v[1]);
        swap(s[mid].sum[0], s[mid].sum[1]);
    }
    rt = merge(h, merge(mid, t));
}
pair<double, double> ask(int l, int r, double x, double y) {
    int h, mid, t;
    pair<double, double> ans;

    split(rt, h, t, r + 1);
    split(h, h, mid, l);
    ans.first = s[mid].sum[0].first.a * x + s[mid].sum[0].first.b * y + s[mid].sum[0].first.c;
    ans.second = s[mid].sum[0].second.a * x + s[mid].sum[0].second.b * y + s[mid].sum[0].second.c;
    rt = merge(h, merge(mid, t));

    return ans;
}

int main() {
    freopen("point.in", "r", stdin);
    freopen("point.out", "w", stdout);

    int n, m;

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int opt;

        scanf("%d", &opt);
        if (opt == 1) {
            double u, v, t;
            double A;

            scanf("%lf %lf %lf", &u, &v, &t);

            A = t * PI / 1800;

            pair<polynomial, polynomial> v1 =
                make_pair(polynomial(cos(A), -sin(A), (1 - cos(A)) * u + v * sin(A)),
                          polynomial(sin(A), cos(A), -u * sin(A) + v * (1 - cos(A))));
            pair<polynomial, polynomial> v2 =
                make_pair(polynomial(cos(-A), -sin(-A), (1 - cos(-A)) * u + v * sin(-A)),
                          polynomial(sin(-A), cos(-A), -u * sin(-A) + v * (1 - cos(-A))));

            insert(v1, v2, i);
        } else if (opt == 2) {
            double u, v, w;

            scanf("%lf %lf %lf", &u, &v, &w);
            insert(make_pair(polynomial((v * v) / (u * u + v * v), -(u * v) / (u * u + v * v),
                                        -u * w / (u * u + v * v)),
                             polynomial(-u * v / (u * u + v * v), (u * u) / (u * u + v * v),
                                        -v * w / (u * u + v * v))),
                   make_pair(polynomial((v * v) / (u * u + v * v), -(u * v) / (u * u + v * v),
                                        -u * w / (u * u + v * v)),
                             polynomial(-u * v / (u * u + v * v), (u * u) / (u * u + v * v),
                                        -v * w / (u * u + v * v))),
                   i);
        }
    }
    for (int i = 1; i <= m; i++) {
        int opt;

        scanf("%d", &opt);
        if (opt == 1) {
            int l, r;
            double u, v;

            scanf("%d %d %lf %lf", &l, &r, &u, &v);
            change(l, r, make_pair(polynomial(1, 0, -u), polynomial(0, 1, -v)),
                   make_pair(polynomial(1, 0, u), polynomial(0, 1, v)), 0);
        } else if (opt == 2) {
            int l, r;
            double u, v, w;

            scanf("%d %d %lf %lf %lf", &l, &r, &u, &v, &w);

            pair<polynomial, polynomial> value =
                make_pair(polynomial(((v * v) - (u * u)) / (u * u + v * v), -2 * u * v / (u * u + v * v),
                                     -2 * u * w / (u * u + v * v)),
                          polynomial(-2 * u * v / (u * u + v * v), ((u * u) - (v * v)) / (u * u + v * v),
                                     -2 * v * w / (u * u + v * v)));

            change(l, r, value, value, 1);
        } else {
            int l, r;
            double x, y;
            pair<double, double> ans;

            scanf("%d %d %lf %lf", &l, &r, &x, &y);
            ans = ask(l, r, x, y);
            printf("%.8lf %.8lf\n", ans.first, ans.second);
        }
    }
}