0

我必须实现格雷厄姆扫描算法。这是我的代码：

    /*
    Graham's algorithm'
    */

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

    #include <stack>
    #include <vector>
    #include <math.h>

    #include <algorithm>
    #include <cstdlib>

    using namespace std;
    struct Tpoint
    {
        int x;
        int y;
    };

    struct AR{
        double alpha;
        double r;
        int i;
    }; 


    bool operator<(AR p, AR q){
        if(p.alpha != p.alpha){
            return p.alpha < p.alpha;
        } else {
            return p.r < p.r;
        }
    }



    int det(Tpoint p1, Tpoint p2, Tpoint p3){
        return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
    }


    int right_turn(stack<Tpoint,vector<Tpoint> > S,Tpoint p3){
        Tpoint p2;
        Tpoint p1;


        p2=S.top();
        S.pop();
        p1=S.top();
        S.push(p2);


        if (det(p1,p2,p3)>0)
        return 0;


        if (det(p1,p2,p3)<0)
        return 1;
    }

    int main(){

        vector<Tpoint> Q;

        //Stos pointów, na końcu zawiera wynik
        stack<Tpoint,vector<Tpoint> > S;

        Tpoint point;


    Tpoint array[]={3,-2, -3,-2, 6,4, -6,1, 4,5, 0,0, 3,4, -3,3, -2,2, 0,6};
    Tpoint point00=array[0];
    int xMax = array[0].x;
    int yMin = array[0].y;
    int i;
    for (i=0; i<10; i++){
        if (array[i].y<yMin){
            if(array[i].x>xMax){
                xMax=array[i].x;
                yMin=array[i].y;
                point00=array[i];


            }
        }
    }

    //sorting section start

    printf("%d %d \n \n",point00.x, point00.y);
    Q.push_back(point00);

    Tpoint arrayCLONE[10];
    AR arrayAR[10];
    for (i=0; i<10; i++){
                arrayAR[i].alpha=0.0;
                arrayAR[i].r=0.0;
                arrayAR[i].i=i;
                arrayCLONE[i] = array[i]; 

                array[i].x-=point00.x;
                array[i].y-=point00.y;

    }



    for (i=0; i<10; i++){
        if ((array[i].x != point00.x) && (array[i].y != point00.y)) {
            arrayAR[i].alpha=atan2(array[i].y, array[i].x);
            arrayAR[i].r=sqrt(array[i].x*array[i].x+array[i].y*array[i].y);


            printf("alpha= %d, r= %d \n",arrayAR[i].alpha,arrayAR[i].r);
            printf("x= %d, y= %d\n",array[i].x, array[i].y);
        }else{

        arrayAR[i].alpha=9999;
        arrayAR[i].r=9999;
        arrayAR[i].i=0;
        }

    }

    sort (arrayAR, arrayAR + 10);

    for (i=0; i<10; i++){
        if (arrayAR[i].alpha<1000){
            Q.push_back(arrayCLONE[arrayAR[i].i]);
        //  printf("i =%d \n",i);
            printf("x =%d \n",arrayCLONE[arrayAR[i].i].x);
            printf("y =%d \n",arrayCLONE[arrayAR[i].i].y);
            printf("_____ \n");

        //  printf("index i =%d \n",arrayAR[i].i);
        }
    }


    //sorting section end


    S.push(Q[0]);
    S.push(Q[1]);
    S.push(Q[2]);

    for (int i=3;i<10; i++){
    while (right_turn(S,Q[i])==1)
        S.pop();
        S.push(Q[i]);
    }


    printf("points: \n");
    while (!(S.empty()))
    {
        point=S.top();
        S.pop();
        printf("(%d,%d) ",point.x,point.y);
    }
        printf("\n..");
        getch();
        return 0;
    }

它不适用于排序部分。函数 _arctan2() 和 _sqrt() 返回较大的值。即 sqrt 返回 -1464986461。为什么会发生？结果，点不是按 alfa 排序的，而是以未知的方式排序的。如果我手动设置点的顺序，算法就可以正常工作。

你能告诉我它不工作的方式吗？

4

2 回答 2

1

您正在尝试将浮点值打印为十进制 (int) 值。

改为这样做：

printf("alpha= %f, r= %f \n",arrayAR[i].alpha,arrayAR[i].r);

%d表示有符号十进制整数。查看printf的文档

%f表示十进制浮点数

于 2013-12-09T23:54:40.370 回答
0

好的，现在它可以工作了：

    /*
    Graham's algorithm'
    */

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

    #include <stack>
    #include <vector>
    #include <math.h>

    #include <algorithm>
    #include <cstdlib>

    using namespace std;
    struct Tpoint
    {
        int x;
        int y;
    };

    struct AR{
        double alpha;
        double r;
        int i;
    }; 


    bool operator<(AR p, AR q){
        if(p.alpha != q.alpha){
            return p.alpha < q.alpha;
        } else {
            return p.r < q.r;
        }
    }



    int det(Tpoint p1, Tpoint p2, Tpoint p3){
        return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
    }


    int right_turn(stack<Tpoint,vector<Tpoint> > S,Tpoint p3){
        Tpoint p2;
        Tpoint p1;


        p2=S.top();
        S.pop();
        p1=S.top();
        S.push(p2);


        if (det(p1,p2,p3)>0)
        return 0;


        if (det(p1,p2,p3)<0)
        return 1;
    }

    int main(){

        vector<Tpoint> Q;

        //Stos pointów, na końcu zawiera wynik
        stack<Tpoint,vector<Tpoint> > S;

        Tpoint point;


    Tpoint array[]={-3,-2, 6,4, -6,1, 4,5, 0,6, 3,4, -3,5, 3,-2,  -2,2, 0,0, 1,1};
    Tpoint point00=array[0];
    int xMax = array[0].x;
    int yMin = array[0].y;
    int i;
    for (i=1; i<9; i++){

        if (array[i].y<yMin){
            yMin=array[i].y;


            }
        }


    for (i=1; i<9; i++){

        if (array[i].y==yMin){
                if(array[i].x>xMax){
                xMax=array[i].x;

                point00=array[i];


            }
        }
    }


    //sorting section start

    printf("point00 x=%d y=%d \n \n",point00.x, point00.y);
    Q.push_back(point00);

    Tpoint arrayCLONE[11];
    AR arrayAR[11];
    for (i=0; i<10; i++){
                arrayAR[i].alpha=0.0;
                arrayAR[i].r=0.0;
                arrayAR[i].i=i;
                arrayCLONE[i] = array[i]; 


                array[i].x-=point00.x;
                array[i].y-=point00.y;

        //printf("x2= %d, y2= %d\n",array[i].x, array[i].y);
    }



    for (i=0; i<11; i++){

        if (((array[i].x != 0) || (array[i].y != 0))) {

            arrayAR[i].alpha=atan2(array[i].y, array[i].x);
            arrayAR[i].r=sqrt(array[i].x*array[i].x+array[i].y*array[i].y);

            arrayAR[i].i=i;
            printf("alpha= %f, r= %f , x= %d, y=%d\n",arrayAR[i].alpha,arrayAR[i].r,array[i].x, array[i].y);

        }else{

        arrayAR[i].alpha=9999;
        arrayAR[i].r=9999;
        arrayAR[i].i=16;
        }

    }

    sort (arrayAR, arrayAR +10);
    Tpoint temp;
    for (i=0; i<10; i++){
        if (arrayAR[i].alpha<1000 && arrayAR[i].alpha>0.0){

            Q.push_back(arrayCLONE[arrayAR[i].i]);
        //  printf("i =%d \n",i);
            printf("x =%d \n",arrayCLONE[arrayAR[i].i].x);
            printf("y =%d \n",arrayCLONE[arrayAR[i].i].y);
            printf("_____ \n");

        //  temp.x=arrayCLONE[arrayAR[i].i].x;
        //  temp.y=arrayCLONE[arrayAR[i].i].y;
        //  printf("index i =%d \n",arrayAR[i].i);
        }
    }

    //Q.push_back(temp);
    //sorting section end


    S.push(Q[0]);
    S.push(Q[1]);
    S.push(Q[2]);

    for (int i=3;i<10; i++){
    while (right_turn(S,Q[i])==1)
        S.pop();
        S.push(Q[i]);
    }

    //  S.push(Q[5]);


    printf("points: \n");
    while (!(S.empty()))
    {
        point=S.top();
        S.pop();
        printf("(%d,%d) ",point.x,point.y);
    }
        printf("\n...");
        getch();
        return 0;
    }
于 2013-12-14T14:24:08.043 回答