【Nyoj298】点的变换

来源和评测点

Nyoj298
Caioj1479

题目

【题目大意】
平面上有不超过10000个点,坐标都是已知的
现在可能对所有的点做以下几种操作:详见输入格式
操作的次数不超过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

分析

首先,假如对每个点一个个进行操作的话,O(NM)显然会超时
那怎么办呢?题目中每个操作都是对所有点而言的,也就是所有点都要经过各种操作
那么考虑用矩阵乘法加速,把每个操作对应的矩阵推导出来就好了
这样有什么好处呢?矩阵乘法不是更慢吗?
答案:可以先将所有操作化为一个非常复杂的操作O(M),再每个点乘一次就好O(N),共计O(M+N)
提示:由于不满足交换律,所以顺序不能变

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
//*******************全局常量*******************
const int MAXN=11000;
const double PI=acos(-1.0);
//*******************全局定义*******************
struct matrix
{
int row,col;
double p[5][5];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************全局变量*******************
matrix pt[MAXN],c[5],ss;
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]+=a.p[i][k]*b.p[k][j];
c.row=n;c.col=p;
return c;
}
matrix pre(int fn)
{
matrix c;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
c.row=c.col=fn;
return c;
}
//*******************主函数*******************
char s[5];
int main()
{
//横坐标加a,纵坐标加b
c[0].p[1][1]=1;c[0].p[2][2]=1;
c[0].p[3][3]=1;c[0].row=c[0].col=3;
//把所有点相对于X轴进行上下翻转
c[1].p[1][1]=1;c[1].p[2][2]=-1;
c[1].p[3][3]=1;c[1].row=c[1].col=3;
//把所有点相对于Y轴进行左右翻转
c[2].p[1][1]=-1;c[2].p[2][2]=1;
c[2].p[3][3]=1;c[2].row=c[2].col=3;
//坐标放大P倍
c[3].p[3][3]=1;c[3].row=c[3].col=3;
//所有点相对坐标原点逆时针旋转一定的角度A(单位是度)
c[4].p[3][3]=1;c[4].row=c[4].col=3;
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
pt[i].row=3;pt[i].col=1;pt[i].p[3][1]=1;
scanf("%lf%lf",&pt[i].p[1][1],&pt[i].p[2][1]);
}
ss=pre(3);
while(m--)
{
scanf("%s",s);
if(s[0]=='M')
{
double a,b;scanf("%lf%lf",&a,&b);
c[0].p[1][3]=a;c[0].p[2][3]=b;
ss=cheng(c[0],ss);//不可调换,操作越晚越左
}
if(s[0]=='X') ss=cheng(c[1],ss);
if(s[0]=='Y') ss=cheng(c[2],ss);
if(s[0]=='S')
{
double p;scanf("%lf",&p);
c[3].p[1][1]=p;c[3].p[2][2]=p;
ss=cheng(c[3],ss);
}
if(s[0]=='R')
{
double a;scanf("%lf",&a);
double rad=PI/180.0*a;//转弧度
c[4].p[1][1]=cos(rad);c[4].p[1][2]=-sin(rad);
c[4].p[2][1]=sin(rad);c[4].p[2][2]=cos(rad);
ss=cheng(c[4],ss);
}
}
for(int i=1;i<=n;i++)
{
pt[i]=cheng(ss,pt[i]);
printf("%.1lf %.1lf\n",pt[i].p[1][1],pt[i].p[2][1]);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/点的变换.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%