| 
 | 
 
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册  
 
x
 
#include<iostream> 
using namespace std; 
 
struct POINT { 
        double x; 
        double y; 
 
}; 
 
double DISTANCE(POINT a, POINT b); 
double CLOSEST(POINT s[], int low, int high); 
double FIND_MINIMUM(double d1, double d2, double d3); 
int QUICKSORT(struct POINT p[],int begin,int end) ; 
int PARTITION(POINT p, int begin, int end); 
int main() { 
        POINT p[10];            //设定点的集合 
        int n; 
        cout << "输入点的个数:\n";      //输入点的个数 
        cin >> n; 
        cout << "输入点集:(x,y)\n"; 
        for (int i = 0; i < n; i++) 
                cin >> p[i].x >> p[i].y; 
        double d=CLOSEST(p, 0,n);      //对输入的点先排序 
        cout << "最小距离为:\n" << d;      //输出点对的最小问题 
        return 0; 
 
} 
double DISTANCE(POINT a, POINT b) { 
        return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); 
} 
 
double FIND_MINIMUM(double d1,double d2) { 
        if (d1 < d2) { 
 
                return  d1; 
        } 
        else if (d2 < d1)  
        { 
                return d2; 
        } 
        return 0; 
} 
double FIND_MINIMUM(double d1, double d2, double d3){ 
        if ((d1 < d2) && (d1 < d3)) { 
         
                return  d1; 
        } 
        else if ((d2 < d1) && (d2 < d3)) 
        { 
                return d2; 
        } 
        else if ((d3 < d1) && (d3 < d2)) { 
                return d3; 
        } 
        return 0; 
} 
double CLOSEST(POINT s[] ,int low , int high ) { 
        double d1; 
        double d2; 
        double d3; 
        double d; 
        POINT *p=new POINT(); 
        if (high - low == 1) { 
                return DISTANCE(s[low], s[high]); 
        } 
        if (high - low == 2) { 
                d1 = DISTANCE(s[low],s[low+1]); 
                d2 = DISTANCE(s[low + 1],s[high]); 
                d3 = DISTANCE(s[low],s[high]); 
                return FIND_MINIMUM(d1,d2,d3); 
        } 
        int middle = (low + high) / 2; 
        d1 = CLOSEST(s, low, middle); 
        d2 = CLOSEST(s, middle + 1, high); 
        d = FIND_MINIMUM(d1,d2); 
        int index = 0; 
        for (int i = middle; (i >= low) && (s[i].x >= s[middle].x - d); i--) { 
 
                p[index++] = s[i]; 
        } 
        for (int j = middle + 1; (j <= high) && (s[j]).x <= s[middle].x + d; j++) { 
                p[index++] = s[j]; 
        } 
        QUICKSORT(p,0,index-1); 
        for (int i = 0; i < index; i++) { 
                for (int j = i + 1; j < index; j++) { 
                        if (p[j].y - p[i].y >= d) { 
                                break; 
                        } 
                        else { 
                                d3 = DISTANCE(p[i],p[j]); 
                                if (d3 < d) { d = d3; } 
                        } 
                 
                 
                 
                } 
        } 
 
        return d; 
} 
         
 
 
int QUICKSORT(POINT p[], int begin, int end) { 
        if (begin < end) { 
                int sign = PARTITION(*p, begin, end); 
                PARTITION(*p,begin,sign-1); 
                PARTITION(*p,sign+1,end); 
        } 
        return 0; 
 
} 
 
int PARTITION(POINT p[], int begin, int end) { 
        double sign_element = p[end].y; 
        int i = begin - 1; 
        for (int j = begin; j < end; j++) { 
                if (p[j].y <= sign_element) { 
                        i++; 
                        exchange(p[i],p[j]); 
                } 
        } 
        exchange(p[i++], p[end]); 
        return i; 
} |   
 
 
 
 |