문제 URL : https://www.acmicpc.net/problem/1007
1007번: 벡터 매칭
평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속
www.acmicpc.net
문제 접근법 :
수학 + 전수 조사 문제입니다.
벡터의 합 + 크기문제입니다. 벡터내용을 수학으로 공부하셨다면 합과 크기 구하는
공식은 쉽습니다.
배우지 않았어도 이공식을 활용하면됩니다. 더 자세한 내용은
출처 :https://j1w2k3.tistory.com/552
[기하와 벡터 이론 07탄] 벡터의 합과 크기
01. 벡터의 합의 크기를 시작하며… 어떤 단원을 배울 때 우리는 기본적인 연산을 위해서 +,-,X,/ 같은 기호에 의미에 대해서 배우게 됩니다. 그리고 그 연산기호를 숙달시키는 연산을 집중적으로
j1w2k3.tistory.com
이블로그의 내용을 참고해주세요
모든벡터들의 길이의 합을 구해야합니다. n이 짝수인 이유도 반드시 점 2개를
선택해야 하니까 그 n개의 점중에 n/2의 개의 두쌍의 점을 선택해서 길이를
벡터의 합으로 표현해 그 크기를 구하는문제입니다. 즉
nCn/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
|
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<double, double>> v;
void input() {
cin >> n;
v = vector<pair<double, double>>(n);
for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;
}
void solve() {
double res = 1e15;
vector<int> p(n, 1);
for (int i = 0; i < n / 2; i++)p[i] = 0;
do {
double sum1 = 0;
double sum2 = 0;
for (int i = 0; i < n; i++) {
sum1 += !p[i] ? -v[i].first : v[i].first;
sum2 += !p[i] ? -v[i].second : v[i].second;
}
res = min(res, pow(sum1 * sum1 + sum2 * sum2, 0.5));
} while (next_permutation(p.begin(), p.end()));
cout << fixed;
cout.precision(12);
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
int test;
cin >> test;
while (test--) {
input();
solve();
}
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 14676 영우는 사기꾼? (0) | 2022.11.15 |
|---|---|
| 백준 5525 IOIOI (0) | 2022.11.01 |
| 백준 피보나치 수 6 (0) | 2022.10.20 |
| 백준 15730 수영장 사장님 (1) | 2022.08.04 |
| 백준 14554 The Other Way (0) | 2022.08.04 |
