The devide and conquer for the Closest Pair Problem

演算法:

給一些平面上的點，找出這些相距最近的兩個點

1. 如果只有一點，回傳距離為無限大

2. 找一直線L垂直X軸並且分割S成一樣大小的兩半SL and SR
    持續分割，直到剩下兩點或一點就進行比較

3. merge時 找出SL 與 SR 兩點之中最小的距離，紀錄為d
    並且在L-d 與 L 裡找所有點a 看有沒有點在 L 與 L+d 裡並且Y值要介於 ay + d  與 ay - d
    如果有判斷它與a 的距離d'是否小於d， 如果小於，則d = d'

程式碼實作如下

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct vertex  //座標資料 
{
    float x;     //紀錄X位置 
    float y;     //紀錄Y位置 
};

struct min_pair //紀錄最短距離pair的資料 
{
    float x1;
    float y1;
    float x2;
    float y2;
    float min_len;   //紀錄最短距離  
};

float len(float x1,float y1,float x2,float y2) //計算兩點間的距離函式 
{
   float result;
   result = sqrt( fabs(x2-x1)*fabs(x2-x1) + fabs(y2-y1)*fabs(y2-y1) );    
   return result;
}

void per( struct vertex *vertex_arr1, int init, int end, struct min_pair *pair1) //per函式將所有點一分為二 init為初始注標 end為結尾注標 
{
    int i,j;
    float result,middle; 
    if( init == end - 1 )  //分割到剩兩點 直接計算距離 
    {   
       result = len(vertex_arr1[init].x, vertex_arr1[init].y, vertex_arr1[end].x, vertex_arr1[end].y); 
       if( result < pair1->min_len )
       {
          pair1->x1 = vertex_arr1[init].x;
          pair1->y1 = vertex_arr1[init].y;
          pair1->x2 = vertex_arr1[end].x;
          pair1->y2 = vertex_arr1[end].y; 
          pair1->min_len = result; 
       }      
    }
    else if(init == end)
        return;
    else
    {
       per(vertex_arr1, init, (init + end )/2, pair1);  //分割後 前半段帶入遞迴 
       per(vertex_arr1, (init + end )/2+1, end, pair1); //分割後 後半段帶入遞迴
       
       //開始merge 
       middle = ( vertex_arr1[(init+end)/2].x + vertex_arr1[(init+end)/2+1].x )/2; //middle紀錄要merge兩區域的中間X值 
       for(i=init;i<=(init+end)/2;i++)
       {
          if( vertex_arr1[i].x <= middle && vertex_arr1[i].x >= middle - pair1->min_len ) //左點的X值位在middle與middle-min_len之間 
          {
             for(j=(init + end)/2+1;j<=end; j++)
             {
                if( vertex_arr1[j].x >= middle && vertex_arr1[j].x <= middle + pair1->min_len ) //右點的X值位在middle+min_len之間 
                {
                   if( vertex_arr1[i].y + pair1->min_len >= vertex_arr1[j].y && vertex_arr1[i].y - pair1->min_len <= vertex_arr1[j].y ) //右點的Y值位在位在左點的Y值+min_len 與y值-min_len之間 
                   {
                      result = len( vertex_arr1[i].x, vertex_arr1[i].y, vertex_arr1[j].x, vertex_arr1[j].y);
                      if( result < pair1->min_len )
                      {
                          pair1->x1 = vertex_arr1[i].x;
                          pair1->y1 = vertex_arr1[i].y;
                          pair1->x2 = vertex_arr1[j].x;
                          pair1->y2 = vertex_arr1[j].y; 
                          pair1->min_len = result; 
                      } 
                   }         
                } 
             }                   
          }
       }
    }              
}

int main()
{
    int i,max=0,j,temp;
    char c[10];
    FILE *fp;
    fp = fopen("input.txt","r+"); 
    
    i=0;
    while(1)    //讀檔 計算有幾個點 
    {
       i++;
       if( fgets(c,10,fp) == NULL )
         break;
    }
    max = i-1; // 共有max個點
    
    fseek(fp,0L,SEEK_SET); //移回檔頭 
    
    struct vertex *vertex_arr = malloc( max * sizeof(struct vertex) );
    struct min_pair *pair = malloc( sizeof(struct min_pair) );
    
    //初始化
    pair->min_len = 1000;
    
    i=0;
    while(1)    //讀檔 並放入vertex 結構 
    {
       fscanf( fp,"%f,%f",&(vertex_arr[i].x) ,&(vertex_arr[i].y) );
       i++;
       if( (getc(fp)) == EOF )
         break;
    }
    
    //先按照X值由小到大排列 
    for(i=0;i<max;i++)
    {
       for(j=i+1;j<max;j++)
       {             
          if( vertex_arr[i].x > vertex_arr[j].x )
          {    
              temp = vertex_arr[i].x;
              vertex_arr[i].x = vertex_arr[j].x;
              vertex_arr[j].x = temp;
              
              temp = vertex_arr[i].y;
              vertex_arr[i].y = vertex_arr[j].y;
              vertex_arr[j].y = temp;
          }
          else if( vertex_arr[i].x == vertex_arr[j].x && vertex_arr[i].y > vertex_arr[j].y )
          {    
              temp = vertex_arr[i].y;
              vertex_arr[i].y = vertex_arr[j].y;
              vertex_arr[j].y = temp;
          }
       }             
    }
    
    per(vertex_arr,0,max-1,pair); //開始遞迴 
    
    printf("%.0f,%.0f\n",pair->x1,pair->y1);
    printf("%.0f,%.0f\n",pair->x2,pair->y2);
    printf("min_len = %.2f\n",pair->min_len);
    

    
    system("pause");
    return 0;
}

輸入請以讀入檔案方式。
例如：以下檔案內容，代表5個平面座標點
2,3
4,5
6,7
8,9
10,11