Graham scan C++ не работает

Question

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

Структура точки, с функцией, чтобы угол между ним и точку с самым низким у и х-координаты

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

сортирует и начинает сканирование Грэхого

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

Answer 1

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

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

Answer 2

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

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

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

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