2010年12月4日 星期六

[C] Closest Pair Problem


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

struct point
{
       double x;
       double y;
};
struct point p[200000];
double length(struct point, struct point);
int cmp(const void *p1, const void *p2);

int main()
{
    FILE *fin;
    char * pEnd;
    char x[200000];   
    int count;
    int i,j;
    int t;
    double d;
    double mind;
    int mi=0,mj=0;  //記錄最短距離兩點座標用
    char key;   //switch case用

    printf("(1)10k point \n");
    printf("(2)50k point \n");
    printf("(3)200k point \n");
    printf("(4)test \n");
    printf("select file : ");
    scanf("%c",&key);   
    switch(key)
    {
       case '1': fin = fopen("p10k.txt","r");
                 count=10000;
                 break;
       case '2': fin = fopen("p50k.txt","r");
                 count=50000;
                 break;
       case '3': fin = fopen("p200k.txt","r");
                 count=200000;
                 break;
       case '4': fin = fopen("test.txt","r");
                 count=10;
                 break;
       default:
                return 0;
    }
   
    if(fin == NULL)
    {
           printf("Fail To Open File !!");
           return;
    }       
       
    for(i=0 ; i<count ; i++)
    {
       if(fgets(x, 1000 , fin) != NULL)
       {   
            p[i].x = strtod(x,&pEnd);    //strtod=將字串轉換為雙精度數值
            p[i].y = strtod(pEnd,NULL);
       }
    }
   
    qsort(p,count,sizeof(struct point),cmp);
    printf("sorting...\n");

    mind = ( (p[0].x - p[1].x)*(p[0].x - p[1].x) +  (p[0].y - p[1].y)* (p[0].y - p[1].y) );
    printf("loading...\n");
   
    for(i=0; i<count ; i++)
    {
        for(j=i+1 ; j<count ; j++)
        {
           if( (p[i].x - p[j].x)*(p[i].x - p[j].x) < mind )   //p[i].x到p[j].x距離平方 若小於mind
            {
                if( (p[i].y - p[j].y)*(p[i].y - p[j].y) < mind )
                {
                    d=( (p[i].x - p[j].x)*(p[i].x - p[j].x) +  (p[i].y - p[j].y)* (p[i].y - p[j].y) );                 
                    if(d<mind)
                    {
                        mi=i;
                        mj=j;
                        mind=d;
                    }
                    else
                        continue;
                }
                else
                    continue;
            }
            else      //此break是因為, 當p[i].x到p[j].x距離已經超過mind了, 所以後面的點可以不用看
                break;
        }
    }   

    mind=sqrt(mind);  //sprt=計算平方根值
   
    printf("mini L: %.2f\n", mind);   
    printf("point:(%.0f , %.0f)\n", p[mi].x, p[mi].y); //p1
    printf("                 to\n");
    printf("point:(%.0f , %.0f)\n", p[mj].x, p[mj].y); //p2
       
    system("pause");
    fclose(fin);
}

int cmp(const void *p1, const void *p2)   //qsort 自訂cmp副程式
{
    return (*(struct point *)p1).x > (*(struct point *)p2).x ? 1 : -1;
}

沒有留言:

張貼留言