代码如下（使用了前缀数组和优化：时间复杂度O(m*n)->O(m+n)）
- 在ccf csp的模拟系统提交的结果一直是错误而且是0分
- 在本地运行正确
- 使用前缀和数组，增加了内存空间的占用，但是没有数量级的提升，时间复杂度由O(m * n)降为O(m+n)
- 易错点：(x,y) ->(r, theta)转换的时候，要注意(x,y)在第一象限（theta = arctan(y/x)）还是第三象限（theta = pi + arctan(y/x)）
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265359
typedef struct Operation {
/*操作结点*/
int type;
double value;
} Operation;
typedef struct Point{
/*被操作的每一个点*/
int idx1;
int idx2;
double x;
double y;
} Point;
typedef struct arrSum{
double k;
double theta;
} arrSum;
void output(arrSum* arrSum1, Point* points, int m);
int main() {
int n, m;
scanf("%d %d", &n, &m);
Operation* ops = (Operation*)malloc(sizeof(Operation) * n);
for (int i = 0; i < n; i++) {
/*输入n个操作*/
scanf("%d %lf", &(ops[i].type), &(ops[i].value));
}
Point* points = (Point*)malloc(sizeof(Point) * m);
for (int i = 0; i < m; i++) {
/*输入m个查询*/
scanf("%d %d %lf %lf", &(points[i].idx1), &(points[i].idx2), &(points[i].x), &(points[i].y));
}
arrSum arrSum1[n+1];
arrSum1[0].k = 1.0;
arrSum1[0].theta = 0.0;
for (int i = 1; i < n+1; i++) {
/*计算前缀和数组*/
if (ops[i-1].type == 1) {
arrSum1[i].k = arrSum1[i-1].k * ops[i-1].value;
arrSum1[i].theta = arrSum1[i-1].theta + 0.0;
} else {
arrSum1[i].k = arrSum1[i-1].k * 1.0;
arrSum1[i].theta = arrSum1[i-1].theta + ops[i-1].value;
}
}
output(arrSum1, points, m);
free(ops);
free(points);
return 0;
}
void output(arrSum* arrSum1, Point* points, int m) {
/*共有m个查询*/
for (int i = 0; i < m; i++) {
Point *ptr = &(points[i]);
double initial_r, initial_theta;
initial_r = sqrt(ptr->x * ptr->x + ptr->y * ptr->y);
if (ptr->x > 0) {
/*计算initial_theta要考虑arc-tan函数的周期是PI*/
initial_theta = atan(ptr->y / ptr->x);
} else {
initial_theta = PI + atan(ptr->y / ptr->x);
}
double final_r = initial_r * (arrSum1[ptr->idx2].k / arrSum1[ptr->idx1 - 1].k);
double final_theta = initial_theta + arrSum1[ptr->idx2].theta - arrSum1[ptr->idx1 - 1].theta;
double final_x = final_r * cos(final_theta);
double final_y = final_r * sin(final_theta);
printf("%.3lf %.3lf\n", final_x, final_y);
}
}
运行结果
