0

我的格雷厄姆扫描代码不起作用，它应该得到凸包的周长。它得到n个点的输入，可以有小数。该算法返回一个高于实际周长的值。

我正在使用我所理解的： http ://en.wikipedia.org/wiki/Graham_scan

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define PI 3.14159265

int nodes;

double xmin=10000000, ymin=10000000, totes=0;

struct ppoint
{
    double x, y, angle;
    void anglemake()
    {
        angle=atan2(y-ymin, x-xmin)*180/PI;
        if(angle<0)
        {
            angle=360+angle;
        }
    }
} np;

点结构，具有使它与具有最低 y 和 x 坐标的点之间的角度的函数

vector<ppoint> ch, clist;

bool hp(ppoint i, ppoint j)
{
    return i.angle<j.angle;
}

double cp(ppoint a, ppoint b, ppoint c)
{
    return ((b.x-a.x)*(c.y-a.y))-((b.y-a.y)*(c.x-a.x));
}

z叉积函数

double dist(ppoint i, ppoint j)
{double vd, hd;
    vd=(i.y-j.y)*(i.y-j.y);
    hd=(i.x-j.x)*(i.x-j.x);
    return sqrt(vd+hd);
}

距离发生器

int main()
{
    scanf("%d", &nodes);
    for(int i=0; i<nodes; i++)
    {
        scanf("%lf%lf", &np.x, &np.y);
        if(np.y<ymin || (np.y==ymin && np.x<xmin))
        {
           ymin=np.y;
            xmin=np.x;
        }
        ch.push_back(np);
    }

获得积分

    for(int i=0; i<nodes; i++)
    {
        ch[i].anglemake();
    }
    sort(ch.begin(), ch.end(), hp);
    clist.push_back(ch[0]);
    clist.push_back(ch[1]);
    ch.push_back(ch[0]);

排序并启动 Graham 扫描

    for(int i=2; i<=nodes; i++)
    {
        while(cp(clist[clist.size()-2], clist[clist.size()-1], ch[i])<0)
        {
            clist.pop_back();
        }
        clist.push_back(ch[i]);
    }

格雷厄姆扫描

    for(int i=0; i<nodes; i++)
    {
        totes+=dist(clist[i], clist[i+1]);
    }

获取周长的长度

    printf("%.2lf\n", totes);
    return 0;
}
4

2 回答 2

1

只是为了感兴趣，在 dist 求和之前打印出节点和 clist.size() 的值。

乍一看，只有当 pop_back 永远不会发生时，clist 才能有节点+1 项。如果是，你有未定义的行为。

于 2013-06-11T20:12:48.633 回答
0

我认为问题出在这里：

for(int i=0; i<nodes; i++)
{
    totes+=dist(clist[i], clist[i+1]);
}

clist只会有剩余的点数，而不是nodes + 1你加载的点数加一。首先存储这个数字是一个错误恕我直言，因为它从点数开始，然后添加一个以关闭循环，然后再次删除点以使船体凸出。只需使用container.size()，一切就清楚了。

另一个注意事项：使用经过检查的 C++ 标准库实现进行调试。这些会警告您未定义的行为，例如访问超出其范围的向量。C++ 是一种语言，它允许您以多种方式自爆，所有这些都以性能为名。这很好，除非在调试时，也就是你想要最好的诊断时。

于 2013-06-11T20:33:20.963 回答