include stdafx include glut include iostream include cmath include loc

#include "stdafx.h"
#include <glut.h>
#include <iostream>
#include <cmath>
#include <locale.h>
#include <conio.h>
#include <vector>

using namespace std;

int *x;
int *y;
vector <int> dots;
int n;

double area_triangle (int q, int i, int next)
{
   return 0.5 * (x[next] * y[q] + x[q] * y[i] + x[i] * y[next] - y[next] * x[q] - y[q] * x[i] - y[i] * x[next]);
}

int point_in_box (int next,int q,int i)
{
	int a = sqrt((x[i]-x[q])*(x[i]-x[q])+(y[i]-y[q])*(y[i]-y[q]));
	int b = sqrt((x[i]-x[next])*(x[i]-x[next])+(y[i]-y[next])*(y[i]-y[next]));
	if(b<a) return 1;
	else return 0;
}

void jarvis ()
{
  int first,q,next;
  double sign;
  // находим самую нижнюю из самых левых точек
  first = 0;
  for(int i = 1; i < n-1; i++)
  {
    if (x[i] < x[first] || (x[i] == x[first] && y[i] < y[first]))
		first = i;
  }
  q = first; // текущая точка
  // добавляем точки в оболочку
  do
  {
	  dots. push_back(q);
	  next = q;

	  for (int i = n - 1; i >= 0; -- i)
            if (x[i] != x[q] || y[i] != y[q])
            {
                sign = area_triangle (q, i, next);

                if (next == q || sign > 0 || (sign == 0 && point_in_box (next, q, i)))
                    next = i;
            }
        q = next;
  }
  while(q!=first);
  int d;
 cout<<endl;
 for (vector<int>::iterator it = dots.begin() ; it!=dots.end() ; ++it)
  {
      d=*it;
	  cout<<x[d]<<" "<<y[d];
	  cout<<endl;
 }
}

void display()
{
	glClear(GL_COLOR_BUFFER_BIT);
	glBegin(GL_LINE_LOOP);
    for (vector<int>::iterator it = dots.begin() ; it!= dots.end(); it++)
     {
		    glColor3f(0, 1, 0);
		    glVertex2f(x[*it], y[*it]);
	}
	glEnd();

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

int main(int argc, char **argv)
{
	 setlocale(LC_ALL,"Rus");
	 cout<<"Ведите количество точек на плоскости:";
	 cin>>n;

	 x = new int [n];
     y = new int [n];
	 
	 for(int i = 0; i < n; i++)
		 {
		      x[i]=rand()%550+30;
			  y[i]=rand()%350+30;
		 }
 
	 for(int i = 0; i < n; i++)
		 {
		      cout<<x[i]<<" ";
			  cout<<y[i]<<endl;
		 }

	 jarvis();

  glutInit(&argc, argv);
  glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
  glutInitWindowSize(600, 400);
  glutCreateWindow("Jarvis");
  glClearColor(0,0,0, 0);
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  glOrtho(0, 600, 400, 0, -1, 1);
  glutDisplayFunc(display);
  glutMainLoop();
	 
	 delete x;
	 delete y;
	 _getch();
	 return 0;
}