[c++] 백준 1007 - 벡터 매칭 [next_permutation]

벡터 매칭 성공

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

---

시작과 끝점이 정해지면 벡터의 합은 일정하다는걸 깨닿는 문제였다.

1,2가 시작점임이 정해지고 3,4가 도착점임이 정해지면 그냥 다 더하면 벡터의 크기가 나온다.

무려 순서가 상관이 없다!

 

따라서 해야할 일은 start지점과 end지점만 정해주면 문제가 한방에 해결이 된다.

 

N개 지점에서 N/2개를 뽑는것이므로 조합이다. nCn/2

이건 next_permutation을 쓰면 간단하게 구할 수 있다. 

 

나도 몰랐는데 next_permutation이 bool식에도 적용이 가능하더라

#include <bits/stdc++.h>
using namespace std;
struct point{double x;double y;};

int main(){
    double x, y, MIN;
    int T,N; cin>>T;
    point points[20];
    while(T--){
        scanf("%d",&N);
        for(int i=0;i<N;i++){scanf("%lf %lf",&points[i].x , &points[i].y);}
        vector<int> ord(N,1);
        for(int i=0;i<N/2;i++) ord[i] = 0;
        MIN = 9999999;
        do{
            x = y = 0;
            for(int i=0;i<N;i++){
                if(ord[i] == 0){x += points[i].x , y+=points[i].y;}
                else {x -= points[i].x , y-=points[i].y;}
            }
            MIN = min(MIN , sqrt(pow(x,2)+pow(y,2)));
        }while(next_permutation(ord.begin(),ord.end()));
        printf("%.8f\n",MIN);
    }
}