алгоритм — сканирование Грэма c ++ не будет работать

Мой код для сканирования Грэма не работает, он должен получить периметр выпуклой оболочки. Он получает ввод 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-Cross

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 Scan

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

0

Решение

Просто для интереса распечатайте значение узлов и clist.size () перед суммированием dist.

На первый взгляд clist может иметь узлы + 1 элемент, только если pop_back никогда не происходит. и если это так, у вас есть неопределенное поведение.

1

Другие решения

Я думаю, что проблема здесь:

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

clist будет иметь только оставшееся количество очков, а не nodes + 1 это количество очков, которые вы загрузили плюс один. Хранение этого числа в первую очередь является ошибкой ИМХО, поскольку оно начинается с количества точек, затем вы добавляете единицу, чтобы закрыть петлю, а затем снова удаляете точки, чтобы сделать корпус выпуклым. Просто используйте container.size() и все понятно.

Еще одно примечание: используйте проверенную реализацию стандартной библиотеки C ++ для отладки. Это предупредило бы вас о неопределенном поведении, таком как доступ к вектору за пределами его диапазона. C ++ — это язык, который позволяет вам по-разному выстрелить себе в ногу, и все это во имя исполнения. Это хорошо и хорошо, разве что при отладке, когда вам нужна лучшая диагностика.

0