BOJ1007: 벡터 매칭

작성일

https://www.acmicpc.net/problem/1007

  • 수학 + 완전탐색 문제
  • 백터의 연산에서 교환법칙이 적용된다는걸 알아야 하는 중요한 교훈
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
#include <bits/stdc++.h>
using namespace std;

struct Point {
  int x, y;
  Point &operator+=(Point& b) {
    x += b.x, y += b.y;
    return *this;
  }
};

class Problem {
  int N;
  long long ans;
  vector<Point> arr;

public:
  void input() {
    scanf("%d", &N);
    arr.resize(N);
    for(int i = 0; i < N; i++)
      scanf("%d%d", &arr[i].x, &arr[i].y);
  }

  void iter(int k, int remain, int picked) {
    if (remain == 0)
      check(picked);
    for(int i = k+1; i < N; i++)
      iter(i, remain-1, picked | (1 << i));
  }

  void check(int picked) {
    Point A = {0,0} , B = {0,0};;
    for(int i = 0; i < N; i++) {
      if(picked & (1 << i))
        A += arr[i];
      else
        B += arr[i];
    }
    long long x = A.x - B.x, y = A.y - B.y;
    ans = min(ans, x*x + y*y);
  }

  double solve() {
    ans = 1e18;
    input();
    iter(-1, N/2, 0);
    return sqrt(ans);
  }
};

int main() {
  int TC;
  scanf("%d", &TC);
  while(TC--) {
    Problem prob;
    printf("%.12lf\n", prob.solve());
  }
}