坐标变换
其一 : 坐标轴的平移 https://www.acwing.com/problem/content/description/5300/
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010;
static ArrayList<int[]> list = new ArrayList<>();
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String[] str = br.readLine().split(" ");
n = Integer.parseInt(str[0]); m = Integer.parseInt(str[1]);
for (int i = 1; i <= n; i++) {
str = br.readLine().split(" ");
int a = Integer.parseInt(str[0]), b = Integer.parseInt(str[1]);
list.add(new int[]{a, b});
}
int dx = 0, dy = 0;
for (int[] item : list) {
dx += item[0];
dy += item[1];
}
for (int i = 1; i <= m; i++) {
str = br.readLine().split(" ");
int x = Integer.parseInt(str[0]), y = Integer.parseInt(str[1]);
out.println((x + dx) + " " + (y + dy));
}
out.flush();
}
}
相关例题
题解代码
import java.util.*;
public class Main {
static final int N = 100010;
/**
* up_dir : 记录方向的改变，用于计算每一步的方向
* dir : 记录该步的方向 0北1东2南3西
* move : 对应方向移动的坐标变化
* set : 存储所有终点的坐标
*/
static int[] dir = new int[N], up_dir = new int[N];
static int[][] move = new int[][] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static HashSet<List<Integer>> set = new HashSet<>();
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = Integer.parseInt(sc.nextLine());
String ops = sc.nextLine();
System.out.println(getAns(ops));
}
static String getOpsString(int len) {
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
int op = random.nextInt(3);
if (op == 0) sb.append('F');
else if (op == 1) sb.append('L');
else sb.append('R');
}
return sb.toString();
}
static int getAns(String ops) {
for (int i = 1; i <= n; i++) {
if (ops.charAt(i - 1) == 'L') up_dir[i] = -1;
else if (ops.charAt(i - 1) == 'R') up_dir[i] = 1;
}
//计算每一步的方向
for (int i = 1; i <= n; i++) dir[i] = ((dir[i - 1] + up_dir[i]) % 4 + 4) % 4;
ArrayList<int[]> list = new ArrayList<>();
int x0 = 0, y0 = 0;
for (int i = 1; i <= n; i++) {
//计算初始情况的终点坐标，并记录每一个到达的点的坐标和操作种类用于下面的左右螺旋操作
list.add(new int[]{x0, y0, ops.charAt(i - 1)});
x0 += move[dir[i]][0];
y0 += move[dir[i]][1];
}
/*
坐标变换添加进hash表中去重，答案即为表的大小
对于F操作：
进行左(L)右(R)螺旋90度
对于L操作：
进行右螺旋90度(F)右螺旋180度(R)
对于R操作：
进行左螺旋90度(F)左螺旋180度(L)
*/
for (int[] item : list) {
int x1 = x0 - item[0], y1 = y0 - item[1];
int[] l, r;
if (item[2] == 'F') {
l = lScrew(x1, y1);
r = rScrew(x1, y1);
} else if (item[2] == 'L') {
l = rScrew(x1, y1);
r = rScrew(l[0], l[1]);
} else {
l = lScrew(x1, y1);
r = lScrew(l[0], l[1]);
}
add(item, l, r);
}
return set.size();
}
/**
* 将重点坐标转换回到原坐标轴并添加进set
* @param item item坐标在原坐标轴下的坐标
* @param r 第一个终点坐标在原坐标轴下的坐标
* @param l 第二个终点坐标在原坐标轴下的坐标
*/
static void add(int[] item, int[] r, int[] l) {
int x = r[0] + item[0], y = r[1] + item[1];
set.add(Arrays.asList(x, y));
x = l[0] + item[0];
y = l[1] + item[1];
set.add(Arrays.asList(x, y));
}
/**
* 右螺旋90度
* @param x 终点的初始坐标(在(item[0], item[1])下的坐标)
* @param y 终点的初始坐标
* @return 终点坐标右螺旋(在(item[0], item[1])下的坐标)
*/
static int[] rScrew(int x, int y) {
int[] res = new int[2];
res[0] = y;
res[1] = -x;
return res;
}
/**
* 左螺旋90度(也可以根据调用右旋来解决)
* @param x 终点的初始坐标(在(item[0], item[1])下的坐标)
* @param y 终点的初始坐标
* @return 终点坐标左螺旋(在(item[0], item[1])下的坐标)
*/
static int[] lScrew(int x, int y) {
int[] res = new int[2];
res[0] = -y;
res[1] = x;
return res;
}
}
acwing相似题: 错误方向 https://www.acwing.com/file_system/file/content/whole/index/content/4184959/
与上题相似
其二 坐标的旋转与伸缩 https://www.acwing.com/file_system/file/content/whole/index/content/10768524/
注意到一个操作是改变与原点的距离，一个操作是改变与x轴所夹成的角度，如果考虑坐标在极坐标系下的表示形式，会发现这两种操作只是分别对其中一维进行操作，且这些操作是可逆的，且不会相互影响。
因此我们就预处理出 ops[i]表示操作 1..i对距离k和角度θ的影响，这是一个前缀和数组。
然后对于一个点问经过操作 l..r的结果，先对它施加1..r操作的影响，再消除 1..l−1操作的影响，即可得到
l..r操作的结果。施加影响，就是长度 ×k，角度 +θ，消除影响，就是长度 /k，角度−θ。
最后根据r和θ还原出x=rcosθ,y=rsinθ。时间复杂度为 O(n+m)。
相关博客 https://blog.csdn.net/weixin_46655675/article/details/133781804
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String[] str = br.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
double x0 = 1, y0 = 1;
ArrayList<Double> k = new ArrayList<>();//前缀乘
ArrayList<Double> xita = new ArrayList<>();//前缀和
k.add(1d);//先给1，方便求解和下标对应
xita.add(0d);//先给0
for (int i = 1; i <= n; i++) {
str = br.readLine().split(" ");
double type = Double.parseDouble(str[0]), value = Double.parseDouble(str[1]);
if (type == 1) {//要这样写法，保证l...r 的一一对应
k.add(k.get(i - 1) * value);
xita.add(xita.get(i - 1));
} else {
k.add(k.get(i - 1));
xita.add(xita.get(i - 1) + value);
}
}
for (int i = 0; i < m; i++) {
str = br.readLine().split(" ");
int l = Integer.parseInt(str[0]), r = Integer.parseInt(str[1]);
double x = Double.parseDouble(str[2]), y = Double.parseDouble(str[3]);
double sum_xita = xita.get(r) - xita.get(l - 1);
double mul_k = k.get(r) / k.get(l - 1);
out.println(getAns(x, y, sum_xita, mul_k));
}
out.flush();
}
static String getAns(double x, double y, double xita, double k) {
return k * (x * Math.cos(xita) - y * Math.sin(xita)) + " " + k * (x * Math.sin(xita) + y * Math.cos(xita));
}
}
