Выпуклый полигон, программа готова, но есть ошибки

[zorg-kirill]

Программа должна выводить против часовой стрелки вершины выпуклого полигона (номера точек по порядку ввода), созданного с помощью введенных координат точек. Ошибка в функции make_2halfs() она должна заносить в верхний массив точки, которые выше указанного уравнения прямой, а в нижний массив точки, которые ниже уравнения, но точки в массив не заносятся(когда программа работает, то между .it. должны быть цифры 1 или 2 но их нет).Помогите найти и исправить ошибку пожалуйста.
p.s. В некоторых функциях я сделал вывод символов/цифр для проверки работоспособности функций

#include <iostream>
#include <math.h>
using namespace std;
int i,j,l=j=1,n,pl_pt_n=4;
float angle=0, wtf;
struct pt
{
	short first_n;
	bool allow;
	float x, y;
};
pt *st, temp,*upper,*lower;
void input()
{
	do
	{
		cout<<"Number of points =";
		cin>>n;
	}
	while (n<3 || n>1000);
	upper=lower=st=new pt[n-1];
	cout<<"Write points' coordinates:";
	for (i=0; i<n; i++)
	{
		st[i].allow=false;
		st[i].first_n=i+1;
		cout<<endl<<i+1<<".\nx=";
		cin>>st[i].x;
		cout<<"y=";
		cin>>st[i].y;
	}
	lower[0]=st[0];
	upper[0]=lower[0];
}
void change (short flag, short a, short b)
{
	if (flag==1)
	{
		temp=st[a];
		st[a]=st[b];
		st[b]=temp;
	}
	if (flag==2)
	{
		temp=lower[a];
		lower[a]=lower[b];
		lower[b]=temp;
	}
	if (flag==3)
	{
		temp=upper[a];
		upper[a]=upper[b];
		upper[b]=temp;
	}
}
void sort_pt()
{
	bool flag;
	while (true)
	{
		flag=false;
		for (i=1; i<n; i++)
			if (st[i-1].x>st[i].x)
			{
				flag=true;
				change(1,i,i-1);
			}
		if (flag==false)
			break;
	}
	while (true)
	{
		flag=false;
		for (i=1; i<n; i++)
			if (st[i-1].x==st[i].x && st[i-1].y>st[i].y)
			{
				flag=true;
				change(1,i,i-1);
			}
		if (flag==false)
			break;
	}
}
float linear_eq()
{
	return st[i].y+(st[i].x-lower[0].x)*(upper[0].y-lower[0].y)/(upper[0].x-lower[0].x); 
		//(st[i].y-lower[0].y)*(lower[0].x-upper[0].x)-(st[i].x-lower[0].x)*(lower[0].y-upper[0].y);
}
void make_2halfs()
{
	cout<<"error:";
	st[0].allow=st[n-1].allow=true;
	upper[0]=st[n-1];
	lower[0]=st[0];
	for (i=1; i<n-1; i++)
		if (st[i].allow==false)
		{
			cout<<".it.";
			wtf=linear_eq();
			if (wtf>st[i].y)
			{
				cout<<"1";
				lower[j]=st[i];
				++j;
			}
			if (wtf<st[i].y)
			{
				cout<<"2";
				upper[l]=st[i];
				++l;
			}
		}
}
float arccos_v(pt a, pt b, pt c)
{
	return acos(((a.x-b.x)*(c.x-b.x)+(a.y-b.y)*(c.y-b.y))
		/sqrt((pow(a.x-b.x,2)+pow(a.y-b.y,2))*(pow(c.x-b.x,2)+pow(c.y-b.y,2))));
}
void find_second_p()
{
	for (i=1; i<j+1; i++)
		if (arccos_v(upper[0],lower[0],lower[i])>angle)
		{
			angle=arccos_v(upper[0],lower[0],lower[i]);
			n=i;
		}
	lower[n].allow=true;
	change(2,1,n);
	angle=0;
	cout<<"\n.second lower point.";
	for (i=1; i<l+1; i++)
		if (arccos_v(lower[0],upper[0],upper[i])>angle)
		{
			angle=arccos_v(lower[0],upper[0],upper[i]);
			n=i;
		}
	upper[n].allow=true;
	change(3,1,n);
	angle=0;
	cout<<"\n.second upper point.";
}
void make_shell()
{
	cout<<"\n.make shell.";
	short a;
	i=2;
	while (true)
	{
		for (a=i; a<j; a++)
			if (arccos_v(lower[i-2],lower[i-1],lower[a])>angle)
			{
				angle=arccos_v(lower[i-2],lower[i-1],lower[a]);
				n=a;
			}
		lower[n].allow=true;
		change(2,i,n);
		i=++n;
		if (i>=j)
			break;
		++pl_pt_n;
		cout<<"1";
	}
	i=2;
	angle=0;
	while (true)
	{
		for (a=i; a<l; a++)
			if (arccos_v(upper[i-2],upper[i-1],upper[a])>angle)
			{
				angle=arccos_v(upper[i-2],upper[i-1],upper[a]);
				n=a;
			}
		upper[n].allow=true;
		change(3,i,n);
		i=++n;
		if (i>=l)
			break;
		cout<<"2";
		++pl_pt_n;
	}
}
void output()
{
	cout<<"Polygon consists of "<<pl_pt_n<<" points:"<<endl;
	for (i=0; i<j; i++)
		if (lower[i].allow==true)
			cout<<lower[i].first_n<<" ";
	for (i=0; i<l; i++)
		if (upper[i].allow==true)
			cout<<upper[i].first_n<<" ";
	cout<<"\n.5.\n";
}
void main()
{
	input();
	sort_pt();
	make_2halfs();
	find_second_p();
	make_shell();
	output();
	system ("pause");
}

[zorg-kirill]

тут (пока) единственная проблема в функции make_2halfs: там в цикле ни одно ни второе условие почему-то не выполняется, хотя на тетради формулу правильно расписывал (да и в интернете такая же формула) для нахождения уравнения прямой.
(это на 1 функцию выше)

[Abstraction]

1) Не хотите убрать глобальные переменные? Самый лёгкий источник трудноуловимых ошибок же.
2) Что у Вас должно выражать linear_eq? Почему Вы считаете, что делить на (upper[0].x-lower[0].x) безопасно? Выводите ли Вы значение wtf для сравнения с ожидаемым?
3) Насколько я понимаю, (st[i].x-lower[0].x)*(upper[0].y-lower[0].y) оказывается равно 0. Почему - с глобальными переменными гадать можно до бесконечности, сам не хочу и Вам не советую.

[zorg-kirill]

понял, постараюсь уменьшить количество глобальных переменных насколько это возможно

[DiemonStar]

1. Выбираете точку, например, с минимальной координатой y и помечаете как начало.
2. Задаёте начальный угол = 0
3. Перебираете все свободные точки и выбираете ту, угол к оси х которой между ей и выбранной ранее точкой относительно начального угла минимален (все углы должны быть 0..2*Pi), выбираете её (пометив как занятую)
4. Устанавливает значение заданного угла равным углу наклона прямой из п.3.
5. Повторяете с п.3 пока угол между заданной точкой и начальной не станет минимальным.

В общем-то всё просто)

[zorg-kirill]

Сделал по-своему - программа работает ПРАВИЛЬНО, выдает правильный ответ но в конце выдает ошибку:

Windows has triggered a breakpoint in paragraph task 6.7(convex shell).exe.

This may be due to a corruption of the heap, which indicates a bug in paragraph task 6.7(convex shell).exe or any of the DLLs it has loaded.

This may also be due to the user pressing F12 while paragraph task 6.7(convex shell).exe has focus.

з.ы. я Ф-12 не нажимал)))

#include <iostream>
#include <math.h>
using namespace std;
short l=2;
int n,pl_pt_n=2;
struct pt
{
	short first_n;
	bool allow;
	float x, y;
};
pt *st,*shell;
void input()
{
	short i;
	do
	{
		cout<<"Number of points =";
		cin>>n;
	}
	while (n<3 || n>1000);
	st=new pt[n-1];
	shell=new pt[n];
	cout<<"Write points' coordinates:";
	for (i=0; i<n; i++)
	{
		st[i].allow=true;
		st[i].first_n=i+1;
		cout<<endl<<i+1<<".\nx=";
		cin>>st[i].x;
		cout<<"y=";
		cin>>st[i].y;
	}
}
void change (short a, short b)
{
	pt temp;
	temp=st[a];
	st[a]=st[b];
	st[b]=temp;
}
void sort_pt()
{
	short i;
	bool flag;
	while (true)
	{
		flag=false;
		for (i=0; i<n-1; i++)
			if (st[i].x>st[i+1].x)
			{
				flag=true;
				change(i,i+1);
			}
		if (flag==false)
			break;
	}
	while (true)
	{
		flag=false;
		for (i=0; i<n-1; i++)
			if (st[i].x==st[i+1].x && st[i].y>st[i+1].y)
			{
				flag=true;
				change(i,i+1);
			}
		if (flag==false)
			break;
	}
	shell[0]=st[0];
}
float arccos_v(pt a, pt b, pt c)
{
	return acos(double(((a.x-b.x)*(c.x-b.x)+(a.y-b.y)*(c.y-b.y))
		/sqrt((pow(a.x-b.x,2)+pow(a.y-b.y,2))*(pow(c.x-b.x,2)+pow(c.y-b.y,2)))));
}
void find_second_p()
{
	float angle=0;
	short i,j;
	pt temp;
	temp=shell[0];
	temp.y+=1;
	for (i=1; i<n; i++)
		if (arccos_v(temp,shell[0],st[i])>angle)
		{
			angle=arccos_v(temp,shell[0],st[i]);
			shell[1]=st[i];
			j=i;
		}
	st[j].allow=false;
}
void make_shell()
{
	bool flag=false;
	float angle;
	short i,j=1;
	while (j!=0)
	{
		if (flag==true)
		{
			shell[l]=st[j];
			st[j].allow=false;
			++l;
			++pl_pt_n;
		}
		angle=0;
		flag=false;
		for (i=0; i<n; i++)
			if (st[i].allow==true && arccos_v(shell[l-2],shell[l-1],st[i])>=angle)
			{
				flag=true;
				j=i;
				angle=arccos_v(shell[l-2],shell[l-1],st[i]);
			}
	}
}
void output()
{
	short i;
	cout<<"Polygon consists of "<<pl_pt_n<<" points:"<<endl;
	for (i=0; i<l; i++)
		cout<<shell[i].first_n<<" ";
}
void main()
{
	input();
	sort_pt();
	find_second_p();
	make_shell();
	output();
	delete st,shell;
	system ("pause");
}