Мой код для сканирования Грэма не работает, он должен получить периметр выпуклой оболочки. Он получает ввод 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;
}
Просто для интереса распечатайте значение узлов и clist.size () перед суммированием dist.
На первый взгляд clist может иметь узлы + 1 элемент, только если pop_back никогда не происходит. и если это так, у вас есть неопределенное поведение.
Я думаю, что проблема здесь:
for(int i=0; i<nodes; i++)
{
totes+=dist(clist[i], clist[i+1]);
}
clist
будет иметь только оставшееся количество очков, а не nodes + 1
это количество очков, которые вы загрузили плюс один. Хранение этого числа в первую очередь является ошибкой ИМХО, поскольку оно начинается с количества точек, затем вы добавляете единицу, чтобы закрыть петлю, а затем снова удаляете точки, чтобы сделать корпус выпуклым. Просто используйте container.size()
и все понятно.
Еще одно примечание: используйте проверенную реализацию стандартной библиотеки C ++ для отладки. Это предупредило бы вас о неопределенном поведении, таком как доступ к вектору за пределами его диапазона. C ++ — это язык, который позволяет вам по-разному выстрелить себе в ногу, и все это во имя исполнения. Это хорошо и хорошо, разве что при отладке, когда вам нужна лучшая диагностика.