include iostream include stack include stdlib include glut include tim

#include <iostream>
#include <stack>
#include <stdlib.h>
#include "glut.h"
#include <time.h>
using namespace std;
 
struct Point
{
    int x;
    int y;
};
Point *points;
Point *pp;
int n, k = 0;
Point p0;
stack<Point> S;
Point nextToTop(stack<Point> &S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}
void 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 convexHull()
{
   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);
   
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);
 
   for (int i = 3; i < n; i++)
   {
      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
         S.pop();
      S.push(points[i]);
   }
   int i = 0;
   cout << endl << "Точки выпуклой оболочки:" << endl;
   while (!S.empty())
   {
       Point p = S.top();
       cout <<  p.x << "\t" << p.y  << endl;
	   pp[i] = p;
       S.pop();
	   ++i;
	   k++;
   }
   cout << endl << "Количество точек выпуклой оболочки: " << k << endl << endl;
}
 void show(){
	glClear(GL_COLOR_BUFFER_BIT);
	glBegin(GL_LINE_LOOP);
	for (int i = 0 ; i < k; i++)
     {
		    glColor3f(0, 1, 0);
			glVertex2f(pp[i].x, pp[i].y);
	}
	glEnd();

	glColor3f(1, 1, 1);
	for (int i = 0; i < n; i++)
    {
       glBegin(GL_TRIANGLE_FAN);
	   glVertex2f(points[i].x, points[i].y);
       float r = 2;
   
	   for (float phi = 0; phi <= 6.30; phi += 0.1)
        {
            float x0 = r * cos(phi);
            float y0 = r * sin(phi);
			glVertex2f(x0 + points[i].x, y0 + points[i].y);
        }
      glEnd();
    }
   glutSwapBuffers();
}

int main(int argc, char **argv)
{
	 setlocale(LC_ALL,"Rus");
	 cout << "Алгоритм Грэхема:" << endl;
	 cout << "Количество точек на плоскости: ";
	 cin >> n;
	 points = new Point [n];
	 pp = new Point [n];
	 srand(time(NULL));
	 for(int i = 0; i < n; i++){
		      points[i].x=rand()%550+30;
			  points[i].y=rand()%350+30;
		 }
 
	 for(int i = 0; i < n; i++){
		      cout<<points[i].x<<"\t";
			  cout<<points[i].y<<endl;
		 }
     convexHull();
	 glutInit(&argc, argv);
	 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
	 glutInitWindowSize(600, 400);
	 glutCreateWindow("Graham");
	 glClearColor(0,0,0,0);
	 glMatrixMode(GL_PROJECTION);
	 glLoadIdentity();
	 glOrtho(0, 600, 400, 0, -1, 1);
	 glutDisplayFunc(show);
	 glutMainLoop();
	 delete []points;
	 delete []pp;
    return 0;
}