鱼C论坛

 找回密码
 立即注册
查看: 1683|回复: 2

求大佬看一下,我写的最近对问题,运行不了

[复制链接]
发表于 2018-11-2 22:39:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-11-3 08:41:36 | 显示全部楼层
你别说你是huster
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-11-3 09:11:28 | 显示全部楼层
你貌似一开始没有对x进行排序,后面只对y排了序。不对x排序的话分low high middle 就没有意义了(你还注释了对输入点对先排序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-6-26 14:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表