Vector2 [C/C++] 백준 #2166 다각형의 면적(벡터) 이번 문제는 기하와 벡터에 대해서 알고 있으면 쉽게 풀 수 있는 문제입니다. 컴퓨터 그래픽 관련해서 자주 쓰이는 기법입니다. 중고등학교 때, 외적(cross product, outer product, vector product)을 배우고 있지만, 실제로 이런데에 쓰일 수 있다는 점들은 잘 모릅니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 세점 O(0,0), A(xA,yA), B(xB,yB)가 있다.. 2023. 4. 12. #1007 벡터 매칭(Mathematics) 이 문제는 Gold II 문제입니다. 처음에는 동적 프로그래밍을 이용한 TSP프로그램인 줄 알고 열심히 짰다가, 예제 결과가 틀렸길래 뭐지 하고 봤었네요. 제가 문제를 풀 때만 해도 Gold I 문제였는데, 그동안 난이도가 떨어졌네요. 어쩐지 벡터 매칭이 문제 이름인데, TSP 문제일리가 없었죠. 그리고 TSP 문제였다면 조금 더 난이도 값이 주어졌을 것 같네요. TSP 문제였다면, 비트매스킹을 써서 동적 프로그래밍으로 답을 해야하죠. 그 귀찮은 프로그래밍을 다 했었는데. 최대 점들의 갯수가 20개이므로, TSP 문제였다고 해도 시간안에 대충 풀었을 듯 합니다. 문제는 2차원 공간상에 점들이 주어지면, 이 점들중 두개씩 짝을 이루어 벡터를 만들었을 때, 그 벡터들의 합이 최소가 되도록 하는 것입니다. 문.. 2019. 12. 20. 이전 1 다음 728x90
