CODEFORCES CONTESTS - Round 965 (Div. 2) - Find K Distinct Points with Fixed Center
A. Find K Distinct Points with Fixed Center
time limit per test1 second memory limit per test256 megabytes
I couldn’t think of a good title for this problem, so I decided to learn from LeetCode.
You are given three integers xc, yc, and k (−100≤xc,yc≤100, 1≤k≤1000).
You need to find k distinct points (x1,y1), (x2,y2), …, (xk,yk), having integer coordinates, on the 2D coordinate plane such that:
- their center∗ is (xc,yc)
- −10^9≤xi,yi≤10^9 for all i from 1 to k It can be proven that at least one set of kk distinct points always exists that satisfies these conditions.
∗∗The center of kk points (x1,y1x1,y1), (x2,y2x2,y2), ……, (xk,ykxk,yk) is (x1+x2+…+xkk,y1+y2+…+ykk)(x1+x2+…+xkk,y1+y2+…+ykk).
Input
The first line contains tt (1≤t≤1001≤t≤100) — the number of test cases. Each test case contains three integers xcxc, ycyc, and kk (−100≤xc,yc≤100−100≤xc,yc≤100, 1≤k≤10001≤k≤1000) — the coordinates of the center and the number of distinct points you must output. It is guaranteed that the sum of kk over all test cases does not exceed 10001000. #### Output For each test case, output kk lines, the ii-th line containing two space separated integers, xixi and yiyi, (−109≤xi,yi≤109−109≤xi,yi≤109) — denoting the position of the ii-th point. If there are multiple answers, print any of them. It can be shown that a solution always exists under the given constraints.
Example InputCopy
1
2
3
4
5
4
10 10 1
0 0 3
-5 -8 8
4 -5 3
OutputCopy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 10
-1 -1
5 -1
-4 2
-6 -7
-5 -7
-4 -7
-4 -8
-4 -9
-5 -9
-6 -9
-6 -8
1000 -1000
-996 995
8 -10
Code
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
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int xc = sc.nextInt();
int yc = sc.nextInt();
int k = sc.nextInt();
long sumX = 0, sumY = 0;
for (int i = 0; i < k - 1; i++) {
// 충분히 작은 값에서 시작
int x = i - 500000;
int y = i - 500000;
System.out.println(x + " " + y);
sumX += x;
sumY += y;
}
// 마지막 점 계산
long lastX = (long)k * xc - sumX;
long lastY = (long)k * yc - sumY;
// 마지막 점의 좌표가 범위를 벗어나지 않도록 보정
lastX = Math.max(-1000000000, Math.min(1000000000, lastX));
lastY = Math.max(-1000000000, Math.min(1000000000, lastY));
System.out.println(lastX + " " + lastY);
}
}
}