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

using namespace std;

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

int point(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
  {
	  parts.push_back(q);
	  next = q;

	  for (int i = n - 1; i >= 0; -- i)
            if (x[i] != x[q] || y[i] != y[q])            {
                sign = 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]);

                if (next == q || sign > 0 || (sign == 0 && point(next, q, i)))
                    next = i;
            }
        q = next;
  }
  while(q!=first);
  int d;
  cout << endl << "Точки выпуклой оболочки:" << endl;
  for (vector<int>::iterator it = parts.begin() ; it!=parts.end() ; ++it){
      d=*it;
	  cout<<x[d]<<" "<<y[d];
	  cout<<endl;
 }
 cout << endl << "Количество точек выпуклой оболочки: " << parts.size() << endl << endl;
}
void show(){
	glClear(GL_COLOR_BUFFER_BIT);
	glBegin(GL_LINE_LOOP);
    for (vector<int>::iterator it = parts.begin() ; it!= parts.end(); it++)
     {
		    glColor3f(1, 0, 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 << "Алгоритм Джарвиса:" << endl;
	 cout << "Количество точек на плоскости: ";
	 cin >> n;

	 x = new int [n];
     y = new int [n];
	 srand(time(NULL));
	 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(700, 500);
	 glutCreateWindow("Jarvis");
	 glClearColor(0,0,0,0);
	 glMatrixMode(GL_PROJECTION);
	 glLoadIdentity();
	 glOrtho(0, 600, 400, 0, -1, 1);
	 glutDisplayFunc(show);
	 glutMainLoop();	 
	 delete x;
	 delete y;
	 _getch();
	 return 0;
}