Divide-and-Conquer for Maxima Finding

演算法:

定義: P1(x1,y1) dominate P2(x2,y2)  if only if x1  >= x2 and y1 >= y2

A point is called a max point if no other point dominate it 

輸入:一些平面上的點

輸出:THE MAXIMAL points

1. if 只有一點, 回傳它就是 max point 
    不然找一直線L垂直X軸 並且分割S成一半 SL and SR

2. 持續遞迴直到剩下兩點或一點， 進行比較

3. 開始merge， 在SR裡找到一點有最大的Y值，記錄它，
    並且在SL裡判斷所有的點的Y值有沒有小於這點的Y，
    如果有，刪除這點

程式碼實作如下

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

struct vertex  //座標資料 
{
    int x;     //紀錄X位置 
    int y;     //紀錄Y位置 
    int max_point;    //紀錄是否為max_point 
};

void per( struct vertex *vertex_arr1, int init, int end) //per函式將所有點一分為二 init為初始注標 end為結尾注標 
{   
    int i,maxy=0,maxx=0;
    if( init == end )  //if分割到只勝一點 將這點指派為max_point 
       vertex_arr1[init].max_point = 1;
    else 
    {
       per(vertex_arr1, init, (init + end )/2);  //分割後 前半段帶入遞迴 
       
       //開始merge 
       for(i=(init + end )/2+1;i<=end;i++)  // 找後半段的最大y值的點   
       {
           if( maxy < vertex_arr1[i].y )
           { 
              maxx = vertex_arr1[i].x; 
              maxy = vertex_arr1[i].y;                     
           } 
       }
       
       for(i=init;i<=(init + end)/2;i++)   // 前半段的點若為max_point 則判斷此點x y值 若小於maxx maxy 則為不合的點 
       {
           if( vertex_arr1[i].max_point == 1 && vertex_arr1[i].x < maxx && vertex_arr1[i].y < maxy )
              vertex_arr1[i].max_point = 0;                    
       }
       
       per(vertex_arr1, (init + end )/2+1, end); //分割後 後半段帶入遞迴 
    }   
}

int main(void)
{
    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; // 算有幾個點
    
    fseek(fp,0L,SEEK_SET); //移回檔頭 
    
    struct vertex *vertex_arr = malloc( max * sizeof(struct vertex) );
    for(i=0;i<max;i++)  //初始化 
    {
       vertex_arr[i].x = -1;
       vertex_arr[i].y = -1;
       vertex_arr[i].max_point = 0;             
    }
    
    i=0;
    while(1)    //讀檔 並放入vertex 結構 
    {
       fscanf( fp,"%d,%d",&(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;
          }
       }             
    }
    
    per(vertex_arr,0,max-1); //開始遞迴 
    
    for(i=0;i<max;i++) //印出max_point 
    {
        if( vertex_arr[i].max_point == 1 )             
          printf("%d,%d\n",vertex_arr[i].x ,vertex_arr[i].y);                      
    }
    system("pause");
    return 0;
} 

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