c++ - Graham Scan C++无法正常工作

Question

我的格雷厄姆扫描代码不工作，它应该得到凸面外壳的周长。它得到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]);

分类并开始格雷厄姆扫描

    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]);
    }

Graham扫描

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

获取周长

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

Answer 1

为了方便起见，在dist求和之前打印出nodes和clist.size（）的值。
一目了然，clist只有在不发生pop_back的情况下才能拥有nodes+1项。如果你有不确定的行为。