坐标变换(其一)
第一题非常简单,只需要把操作进行整合,对于每一个查询都是一样的操作。
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a=0,b=0;
while(n--){
int dx,dy;
cin>>dx>>dy;
a+=dx;
b+=dy;
}
while(m--){
int x,y;
cin>>x>>y;
cout<<x+a<<" "<<y+b<<endl;
}
return 0;
}
坐标变换(其二)
思路非常简单。
方法一
暴力(80分),时间复杂度$O(n^2)$
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
typedef pair<int,double> PII;
int n,m;
int main(){
scanf("%d%d",&n,&m);
vector<PII> v;
for(int i=0;i<n;i++){
int op;
double x;
cin>>op>>x;
v.push_back({op,x});
}
while(m--){
int i,j;
double x,y;
cin>>i>>j>>x>>y;
for(int k=i-1;k<=j-1;k++){
if(v[k].first==1) {
x*=v[k].second,y*=v[k].second;
}
else {
double tx,ty;
tx=x*cos(v[k].second)-y*sin(v[k].second);
ty=x*sin(v[k].second)+y*cos(v[k].second);
x=tx;
y=ty;
}
}
printf("%.3llf %.3llf",x,y);
if(m) printf("\n");
}
return 0;
}
方法二
运用前缀和算法(100分),时间复杂度$O(n)$,并且,我们为了减少浮点数运算次数,可以采用极坐标的方式去做题,然后最后输出的时候再转换为直角坐标,当然都是满分。我的代码在官网上是满分,在y总这网站上segmentation fault,只需要把最后一条语句改为cout就正确了,这点不知道为什么。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100010;
//用极坐标,可以减少浮点数的操作次数
//两个前缀和数组,第一个累乘,第二个累加
double k[N],theta[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
//因为是累乘
k[0]=1;
for(int i=1;i<=n;i++){
int op;
double num;
scanf("%d%lf",&op,&num);
if(op==1) k[i]=k[i-1]*num,theta[i]=theta[i-1];
else k[i]=k[i-1],theta[i]=theta[i-1]+num;
}
while(m--){
int i,j;
double x,y;
scanf("%d%d%lf%lf",&i,&j,&x,&y);
printf("%lf %lf\n",sqrt(x*x+y*y)*k[j]/k[i-1]*cos(atan2(y,x)+theta[j]-theta[i-1]),sqrt(x*x+y*y)*k[j]/k[i-1]*sin(atan2(y,x)+theta[j]-theta[i-1]));
}
return 0;
}
暴力代码运行有问题
官网应该是可以的,我都提交过,acwing上不知道情况