점들중 가장 가까운 점을 구하는 알고리즘 질문입니다.
조회수 2818회
실행환경은 Bash를 통한 GCC컴파일러를 사용합니다. 16개의 점들중에 서로 가장 가까운 두 점의 거리를 구하는 프로그램을 만드려고 합니다.
#include <stdio.h>
#include <math.h>
#define NUM_OF_DOTS 16
#define MIN(x,y) ((x < y) ? x : y)
// 점 구조체
typedef struct {
int x;
int y;
}DOT;
// 거리 구하기
double distance (DOT a, DOT b) {
double delta_x = a.x - b.x;
double delta_y = a.y - b.y;
return sqrt(delta_x * delta_x + delta_y * delta_y);
}
//세 수중 최소값
double min(double a, double b, double c) {
int t;
t = (a < b) ? a : b;
t = (t < c) ? t : c;
return t;
}
//합병정렬
void Merge(DOT *arr , int f, int mid, int l)
{
DOT temp[16];
int first1 = f; int last1 = mid;
int first2 = mid+1; int last2 = l;
int index = first1;
for(;(first1<=last1)&&(first2<=last2); ++index)
{
if(arr[first1].x < arr[first2].x)
{
temp[index] = arr[first1];
++first1;
}
else
{
temp[index] = arr[first2];
++first2;
}
}
for(; first1 <= last1; ++first1, ++index)
temp[index] = arr[first1];
for(; first2 <= last2; ++first2, ++index)
temp[index] = arr[first2];
for(index = f; index<=l; ++index)
arr[index] = temp[index];
}
void Mergesort(DOT * arr , int first, int last)
{
if(first < last)
{
int middle = (first+last)/2;
Mergesort(arr,first,middle);
Mergesort(arr,middle+1,last);
Merge(arr, first,middle,last);
}
}
//ClosestPair 함수
//Area는 점들이 모여있는 영역, start~end는 인덱스 기준으로 시작과 끝 범위.
//입력되는 Area 내의 점들은 x축 값을 기준으로 오름차순 되어야 함.
double ClosestPair(DOT * Area, int start, int end) {
//반복용 임시변수
int i, j;
//왼쪽 영역의 최소 길이
double left_side;
//오른쪽 영역의 최소 길이
double right_side;
//중간에 나뉘어지는 두 점의 길이
double middle_side;
//인덱스 범위 차 = (실제 개수) - 1
int D = (end-start);
//거리 지역변수
double dist;
if(D < 2) //점이 2개만 존재하면,
return distance(Area[start], Area[end]);
else { //점이 3개 이상이면 나눈다
if(D % 2) { // 개수가 홀수이면
left_side = ClosestPair(Area, start, (start + end)/2 );
right_side = ClosestPair(Area, (start + end)/2 + 1 , end);
dist = MIN(left_side, right_side);
//중간거리 구하기
//오른쪽 범위 구하기
i = 0;
while(1){
double mid_distance_right = distance(Area[start + (D/2) - 1], Area[start + (D/2) + i]);
if(mid_distance_right < dist) i++;
else break;
}
//왼쪽 범위 구하기
j = 0;
while(1){
double mid_distance_left = distance(Area[start + (D/2) - j], Area[start + (D/2)]);
if(mid_distance_left < dist) j++;
else break;
}
middle_side = distance(Area[start + (D/2) - j], Area[start + (D/2) + i]);
return min(left_side, right_side, middle_side);
}
else { //개수가 짝수이면
left_side = ClosestPair(Area, start, start + (D/2));
right_side = ClosestPair(Area, start + (D/2) + 1, end);
dist = MIN(left_side, right_side);
//중간거리 구하기
//오른쪽 범위 구하기
i = 0;
while(1){
double mid_distance_right = distance(Area[start + (D/2)], Area[start + (D/2) + i]);
if(mid_distance_right < dist) i++;
else break;
}
//왼쪽 범위 구하기
j = 0;
while(1){
double mid_distance_left = distance(Area[start + (D/2) - j], Area[start + (D/2) + 1]);
if(mid_distance_left < dist) j++;
else break;
}
middle_side = distance(Area[start + (D/2) - j], Area[start + (D/2) + i]);
return min(left_side, right_side, middle_side);
}
}
}
int main() {
DOT Area[NUM_OF_DOTS] = {{10,15}, {5,15}, {20,3}, {6,1}, {9,7}, {15,9}, {8,15}, {20,14}, {17,13}, {16,11}, {7,12}, {10,10}, {1,19}, {8,8}, {30,9}, {22,4}};
Mergesort(Area , 0, 15); //정렬
printf("%lf",sqrt(ClosestPair(Area,0,15)));
return 0;
}
이 코드는 1.414214
의 값이 출력되어 정상적으로 실행하는듯 보였지만,
점의 위치를 바꾸어도 계속 같은 값인 1.414214
으로 출력됩니다.
혹시 어느 부분에서 잘못되었는지 확인할 수 있을까요?
-
(•́ ✖ •̀)
알 수 없는 사용자
1 답변
-
DOT Area[NUM_OF_DOTS] = {{130,145}, {15,153}, {420,35}, {66,14}, {93,71}, {215,39}, {458,1345}, {201,114}, {137,143}, {156,161}, {77,812}, {910,170}, {16,195}, {448,38}, {320,93}, {242,34}};
이런식으로 점을 전부 다 바꾸니 답이 다르게 나옵니다. 아마도 질문작성자님은, 점들 중 가장 가까운 거리를 결정짓는 두 점은 그대로 두고 다른애들만 바꿔서가 아닐까 싶습니다.
근데 점이 16개밖에없는데 굳이 이렇게 힘들게 짜신 이유가 궁금하네요..
#include <stdio.h> #include <math.h> #define NUM_OF_DOTS 16 typedef struct{ int y; int x; } DOT; int main() { int i, j; double min_dist = 1234567890; DOT Area[NUM_OF_DOTS] = {{10,15}, {5,15}, {20,3}, {6,1}, {9,7}, {15,9}, {8,15}, {20,14}, {17,13}, {16,11}, {7,12}, {10,10}, {1,19}, {8,8}, {30,9}, {22,4}}; for(i = 0 ; i < NUM_OF_DOTS - 1 ; i++) { for(j = i + 1 ; j < NUM_OF_DOTS ; j++) { double delta_x = Area[i].x - Area[j].x; double delta_y = Area[i].y - Area[j].y; double dist = sqrt(delta_x * delta_x + delta_y * delta_y); if(dist < min_dist) min_dist = dist; } } printf("%lf\n", min_dist); return 0; }
-
(•́ ✖ •̀)
알 수 없는 사용자
-
댓글 입력