Алгоритм грэхема - C++ - Ответ 5543676

#include <iostream>
#include <stack>
#include <stdlib.h>
#include <time.h>
#include <winbgim.h>
 
using namespace std;
struct Point
{
    int x;
    int y;
};
Point p0;
Point nextToTop(stack<Point>&S)
{
    Point p=S.top();
    S.pop();
    Point res=S.top();
    S.push(p);
    return res;
}
int swap(Point &p1,Point &p2)
{
    Point temp=p1;
    p1=p2;
    p2=temp;
}
int dist(Point p1,Point p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y)*(r.x - q.x)-(q.x - p.x)*(r.y - q.y);
    if (val==0) return 0;
    return (val>0)? 1:2;
}
int compare(const void *vp1, const void *vp2)
{
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
   int o=orientation(p0,*p1,*p2);
   if (o==0)
     return (dist(p0,*p2)>=dist(p0,*p1))? -1 : 1;
   return (o==2)? -1: 1;
}
void Hull(Point points[],int n)
{
   int ymin=points[0].y,min = 0;
   for (int i=1; i<n; i++)
   {
     int y=points[i].y;
     if ((y<ymin) || (ymin==y && points[i].x<points[min].x))
        ymin=points[i].y, min=i;
   }
   swap(points[0], points[min]);
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare);
   stack<Point> S;
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);
   for (int i = 2; i < n; i++)
   {
      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
         S.pop();
      S.push(points[i]);
   }
   int graphdriver = DETECT, gmode;
    initgraph(&graphdriver, &gmode, "");
    if(graphresult() != grOk)
    {
       cout<<"Error\n";
       getch();
    }
    //setbkcolor(WHITE);
    cleardevice();
    int t[n];
    int j=0,c=0,d=0;
    int u[n];
    cout<<"\npoints out:\n";
   while (!S.empty())
   {
       Point p = S.top();
       cout << "(" << p.x << ", " << p.y <<")" << endl;
       t[j]=p.x;
       u[j]=p.y;
       j++;
       S.pop();
   }
for(int c=0;c<j;c++) cout<< "\n((" << t[c] << ", " << u[c] <<"))" << endl;
for(int h=0;h<n;h++) circle(points[h].x,points[h].y,1);
d=0;
while ((d)<j-1)
   {
       line(t[d],u[d],t[d+1],u[d+1]);
       d++;
   }
line(t[j-1],u[j-1],t[0],u[0]);
getch();
closegraph();
}
 
int baba()
{
    M:
    int f,n=0,s=0;
    cout<<"points->";
    cin>>f;
    if(f>2)
    {
    Point points[f];
    srand(time(NULL));
    cout<<"Points:\n";
    for(int c=0;c<f;c++)
    {
        points[c].x=rand()%330+130;
        points[c].y=rand()%300+100;
        cout << "(" << points[c].x << ", " << points[c].y <<")" << endl;
    }
    Hull(points, f);
    }else goto M;
    return 0;
}
int main()
{
    M:
    int f,n=0,s=0;
    cout<<"points->";
    cin>>f;
    if(f>2)
    {
    Point points[f];
    srand(time(NULL));
    cout<<"Points:\n";
    for(int c=0;c<f;c++)
    {
        points[c].x=rand()%330+130;
        points[c].y=rand()%300+100;
        cout << "(" << points[c].x << ", " << points[c].y <<")" << endl;
    }
    Hull(points, f);
    }else goto M;
    return 0;
}