时间限制：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
-
View Code
1 #include<stdio.h>
2 #include<math.h>
3 #define Max 10005
4 #define Pi acos(-1.0)
5 int main()
6 {
7 int n,m,i,j;
8 char ch;
9 double a,b,e1,e2,r;
10 double x[3]={0,1,0};//三个点A,B,C
11 double y[3]={0,0,1};
12 double ch1[Max],ch2[Max],ch3[Max];//分别存放这N个点到A,B,C三点的距离的下平方
13 scanf("%d%d",&n,&m);
14 for(i=0;i<n;i++)//读入n个点分别计算这n个点到A,B,C三点的距离
15 {
16 scanf("%lf%lf",&a,&b);
17 ch1[i]=a*a+b*b;
18 ch2[i]=(a-1)*(a-1)+b*b;
19 ch3[i]=a*a+(b-1)*(b-1);
20 }
21 for(j=0;j<m;j++)//计算A,B,C三个点经过m次变换后得到的三个点A1,B1,C1
22 {
23 getchar();
24 scanf("%c",&ch);
25 if(ch=='X')
26 {
27 for(i=0;i<3;i++)
28 y[i]=-y[i];
29 }
30 else if(ch=='Y')
31 {
32 for(i=0;i<3;i++)
33 x[i]=-x[i];
34 }
35 else if(ch=='M')
36 {
37 scanf("%lf%lf",&a,&b);
38 for(i=0;i<3;i++)
39 {x[i]=x[i]+a;y[i]=y[i]+b;}
40 }
41 else if(ch=='S')
42 {
43 scanf("%lf",&a);
44 for(i=0;i<3;i++)
45 {x[i]=x[i]*a;y[i]=y[i]*a;}
46 }
47 else if(ch=='R')
48 {
49 scanf("%lf",&a);
50 e2=a/180*Pi;
51 for(i=0;i<3;i++)
52 {
53 r=sqrt(x[i]*x[i]+y[i]*y[i]);
54 if(r!=0)
55 {
56 e1=acos(x[i]/r);
57 if(y[i]<0) e1=-e1;
58 x[i]=r*cos(e1+e2);
59 y[i]=r*sin(e1+e2);
60 }
61 }
62 }
63 }
64 double f1,f2,g1,g2,c1,c2,ansy,ansx,p,q,d,fg,ff;//根据A1,B1,C1这三个点的位置和第二步中得到的点到这三个点的距离，确定这N个点的位置
65 f1=2*(x[0]-x[1]);f2=2*(x[0]-x[2]);
66 g1=2*(y[0]-y[1]);g2=2*(y[0]-y[2]);
67 c1=x[0]*x[0]-x[1]*x[1]+y[0]*y[0]-y[1]*y[1];
68 c2=x[0]*x[0]-x[2]*x[2]+y[0]*y[0]-y[2]*y[2];
69 d=(x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]);
70 fg=(f2*g1-f1*g2);ff=f1+f2;
71 for(i=0;i<n;i++)
72 {
73 p=(ch2[i]-ch1[i])*d+c1;q=(ch3[i]-ch1[i])*d+c2;
74 ansy=(f2*p-f1*q)/fg;
75 ansx=(p+q-(g1+g2)*ansy)/ff;
76 if(ansx<0.05&&ansx>-0.05)//考虑精度问题
77 ansx=0;
78 if(ansy<0.05&&ansy>-0.05)
79 ansy=0;
80 printf("%.1lf %.1lf\n",ansx,ansy);
81 }
82
83 return 0;
84 }
