任意门：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=298
点的变换
时间限制：2000 ms | 内存限制：65535 KB
难度：5
- 描述
-
平面上有不超过10000个点，坐标都是已知的，现在可能对所有的点做以下几种操作：
平移一定距离(M)，相对X轴上下翻转(X)，相对Y轴左右翻转(Y),坐标缩小或放大一定的倍数(S),所有点对坐标原点逆时针旋转一定角度(R)。
操作的次数不超过1000000次，求最终所有点的坐标。
提示：如果程序中用到PI的值，可以用acos(-1.0)获得。
- 输入
- 只有一组测试数据
测试数据的第一行是两个整数N,M，分别表示点的个数与操作的个数(N<=10000,M<=1000000)
随后的一行有N对数对，每个数对的第一个数表示一个点的x坐标，第二个数表示y坐标，这些点初始坐标大小绝对值不超过100。
随后的M行，每行代表一种操作，行首是一个字符：
首字符如果是M,则表示平移操作，该行后面将跟两个数x,y，表示把所有点按向量(x,y)平移;
首字符如果是X，则表示把所有点相对于X轴进行上下翻转;
首字符如果是Y，则表示把所有点相对于Y轴进行左右翻转;
首字符如果是S，则随后将跟一个数P,表示坐标放大P倍;
首字符如果是R，则随后将跟一个数A,表示所有点相对坐标原点逆时针旋转一定的角度A(单位是度) - 输出
- 每行输出两个数，表示一个点的坐标(对结果四舍五入到小数点后1位，输出一位小数位）
点的输出顺序应与输入顺序保持一致 - 样例输入
-
2 5
1.0 2.0 2.0 3.0
X
Y
M 2.0 3.0
S 2.0
R 180 - 样例输出
-
-2.0 -2.0
0.0 0.0
题意概括：如题干
解题思路：
点的变换即向量的变换，即转换为矩阵运算，因为就是做初等变换嘛。
AC code：
//题目链接 http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=298
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
const int MAXN = ;
const int MAXS = 1e4+;
const double pi = acos(-1.0);
int N, M; struct mat
{
double m[MAXN][MAXN];
}base;
mat pp[MAXS]; mat muti(mat a, mat b)
{
mat res;
memset(res.m, , sizeof(res.m));
for(int i = ; i <= ; i++){
for(int j = ; j <= ; j++)
if(a.m[i][j]){
for(int k = ; k <= ; k++)
res.m[i][k] = (res.m[i][k] + a.m[i][j] * b.m[j][k]);
}
}
return res;
} mat add(mat a, mat b)
{
mat res;
memset(res.m, , sizeof(res.m));
for(int i = ; i <= ; i++){
for(int j = ; j <= ; j++){
res.m[i][j] = (a.m[i][j] + b.m[i][j]);
}
}
return res;
} //mat qpow(mat a, int n)
//{
// mat res;
// memset(res.m, 0, sizeof(res.m));
// for(int i = 1; i <= 3; i++) res.m[i][i] = 1;
//
// while(n){
// if(n&1) res = muti(res, a);
// n>>=1;
// a = myti(a, a);
// }
// return res;
//} int main()
{
char com;
mat tmp;
double a, b;
scanf("%d %d", &N, &M);
for(int i = ; i <= N; i++){
scanf("%lf %lf", &a, &b);
pp[i].m[][] = a;
pp[i].m[][] = b;
pp[i].m[][] = ;
}
memset(tmp.m, , sizeof(tmp.m));
for(int i = ; i <= ; i++) tmp.m[i][i] = ;
while(M--){
memset(base.m, , sizeof(base.m));
for(int i = ; i <= ; i++) base.m[i][i] = ;
getchar();
scanf("%c", &com);
if(com == 'M'){
scanf("%lf %lf", &a, &b);
base.m[][] = a;
base.m[][] = b;
}
else if(com == 'X'){
base.m[][] = -;
}
else if(com == 'Y'){
base.m[][] = -;
}
else if(com == 'S'){
scanf("%lf", &a);
base.m[][] = a;
base.m[][] = a;
}
else if(com == 'R'){
scanf("%lf", &a);
a = a/*pi;
base.m[][] = cos(a);
base.m[][] = -sin(a);
base.m[][] = sin(a);
base.m[][] = cos(a);
}
tmp = muti(base, tmp);
}
mat ans;
for(int i = ; i <= N; i++){
// pp[i] = muti(tmp, pp[i]);
// printf("%.1f %.1f\n", pp[i].m[1][1], pp[i].m[2][1]);
ans = muti(tmp, pp[i]);
printf("%.1f %.1f\n", ans.m[][], ans.m[][]);
}
return ;
}