1007 vector matching
알고리즘
1
2
3
4
1. 각 테스트 케이스 별로 모든 x좌표와 y좌표를 더함
2. n/2개의 점을 고르고, 그 고른 점들의 모든 x좌표와 y좌표를 더함
3. 1에서 구한 x,y 에 2에서 구한 x,y를 2곱하고 뺌. (sumOfEveryX - 2*sumOfChoosedX)
4. 3.에서 구한 벡터의 길이를 구한 후 반환. 반환 받은 곳은 최솟값을 다시 반환
설명
1
2
들어오는 점들이 짝수이고, 두개씩 짝 지어준다면 벡터를 구했을 때 반은 더하는 형태이고, 반은 빼는 형태이다.
따라서 빼줄 반을 고르고, 전체 X의 합에서 빼면 됨. 근데 전체 X의 합이므로 빼줄 반은 두배로 곱하고 빼야한다.
삽질과정
1
2
3
4
5
처음에 모든 쌍을 지어주고, 모든 방향을 검사하여 길이를 구해도 시간안에 될 줄 알았음
-> 하지만 계산해보니 미친듯이 시간이 많이 걸림
-> 다른 방법으로 빠르게 전환했어야했다
그리고 문제를 푸는데 머리로만 푸는 버릇이 들었는데 이걸 고치고 이런 수학적인 문제는 적으면서 풀어보자.
교훈
1
2
1. 생각난 알고리즘이 있으면 한번 복잡도 계산해보자
2. 수학적인 문제의 경우 식을 적으면서 풀어보자.
코드
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
typedef struct Point {
int x;
int y;
} Point;
vector<vector<Point>> tc;
vector<Point> currentPoint;
int sumOfEveryX, sumOfEveryY;
void generateTc();
long double solveSingleTC(vector<int> choosed, int deep);
int main() {
int numOfTc;
cin >> numOfTc;
for (int i = 0; i < numOfTc; i++) {
int numOfPoint;
cin >> numOfPoint;
vector<Point> tempPoint;
for (int j = 0; j < numOfPoint; j++) {
int x, y;
cin >> x >> y;
tempPoint.push_back({ x, y });
}
tc.push_back(tempPoint);
}
generateTc();
}
void generateTc() {
for (int i = 0; i < tc.size(); i++) {
currentPoint = tc[i];
sumOfEveryX = 0;
sumOfEveryY = 0;
for (int j = 0; j < currentPoint.size(); j++) {
sumOfEveryX += currentPoint[j].x;
sumOfEveryY += currentPoint[j].y;
}
vector<int> choosed;
cout << "test" << endl;
cout.precision(50);
cout << solveSingleTC(choosed, 0) << endl;
}
}
long double solveSingleTC(vector<int> choosed, int deep) {
if (choosed.size() == currentPoint.size() / 2) {
long long sumOfChoosedX = 0;
long long sumOfChoosedY = 0;
for (int i = 0; i < choosed.size(); i++) {
sumOfChoosedX += currentPoint[choosed[i]].x;
sumOfChoosedY += currentPoint[choosed[i]].y;
}
long long length = (sumOfEveryX - 2 * sumOfChoosedX) * (sumOfEveryX - 2 * sumOfChoosedX) +
(sumOfEveryY - 2 * sumOfChoosedY) * (sumOfEveryY - 2 * sumOfChoosedY);
return sqrt(length);
}
else if (currentPoint.size() - deep < (currentPoint.size() / 2) - choosed.size())
return 2000000000;
long double a = solveSingleTC(choosed, deep + 1);
choosed.push_back(deep);
long double b = solveSingleTC(choosed, deep + 1);
return a < b ? a : b;
}