program convexe;

	const
		MAX = 40;
	type
		EnsemblePoint = array[1..MAX] of Point;
		ListePoint = ^boite;
		boite = record
				point: Point;
				pred: ListePoint;
				succ: ListePoint;
			end;

	var
		t: EnsemblePoint;
		l: ListePoint;
		origine, D: Point;
	   {origine O,  un point interieur a l'enveloppe convexe}
           {D est l'autre point qui determine la demi-droite}
		n: integer;
	   {n sera le nombre de points saisis}
		r: Rect;


{--------------------Saisie des points------------------------------}

	procedure GetPoint (var p: Point);
		const
			r = 2;

	begin
		while not button do
			;
		while button do
			;
		GetMouse(p);
		PaintCircle(p.h, p.v, r);
	end;

	function EntrePoints (var t: EnsemblePoint): integer;
		var
			n: integer;
			x0, y0: integer;
	begin
		x0 := -1;
		y0 := -1;
		n := 0;
		repeat
			if n > 0 then
				begin
					x0 := t[n].h;
					y0 := t[n].v;
				end;
			n := n + 1;
			GetPoint(t[n]);
		until (n >= MAX) or ((t[n].h = x0) and (t[n].v = y0));
		if n < MAX then
			n := n - 1;
		EntrePoints := n
	end;

{-----------------Teste si trois points sont alignes-----------------------}
	function determinant (O, p, q: Point): longint;
{calcule le determinant des vecteurs  0p et Oq }
		var
			x, y, z, t: longint;
	begin
		x := p.h - O.h;
		y := p.v - O.v;
		z := q.h - O.h;
		t := q.v - O.v;
		determinant := x * t - y * z;
	end;

	function scalaire (O, p, q: Point): longint;
{calcule le produit scalaire des vecteurs Op et Oq}
		var
			x, y, z, t: longint;
	begin
		x := p.h - O.h;
		y := p.v - O.v;
		z := q.h - O.h;
		t := q.v - O.v;
		scalaire := x * z + y * t;
	end;

	function aligne (p1, p2, p3: Point): boolean;
{renvoie vrai si les points sont alignes et faux sinon}
	begin
		aligne := (determinant(p1, p2, p3) = 0);
	end;

{---------------Choix d'une origine 0 interieure a l'enveloppe--------------------}

	function calcul_origine (var p: EnsemblePoint; var origine: point): boolean;
{La fonction renvoie faux si tous les points sont alignes et vrai sinon}
{Si la valeur renvoyee est vraie, la variable origine contiendra un point interieur}
		var
			i: integer;
			resultat, b: boolean;
	begin
		if (n > 2) then
			begin
				i := 0;
				resultat := false;
				b := false;
				repeat
					begin
						i := i + 1;
						resultat := not (aligne(t[i], t[i + 1], t[i + 2]));
						b := resultat or (i = n - 2);
					end
				until b;
				calcul_origine := resultat;
				if (resultat) then
					begin
						origine.h := round((t[i].h + t[i + 1].h + t[i + 2].h) / 3);
						origine.v := round((t[i].v + t[i + 1].v + t[i + 2].v) / 3);
					end;
			end
		else
			calcul_origine := false;
	end;


{--------------------------tri des points---------------------------------}

	function inferieur (O, p1, p, q: Point): boolean;
{Teste si p est inferieur a q pour l'ordre polaire relatif a la demi droite Op1}
{Ce code peut etre optimise}
		var
			d: longint;
			b: boolean;
	begin
     {si O,p,q alignes du meme cote par rapport a 0, p avant q si Op superieur a Oq}
     {le cas p et q alignes : }
		if (determinant(O, p, q) = 0) then
			begin
				if (scalaire(O, p, q) > 0) then
					begin
						d := ((p.h - O.h) * (p.h - O.h) + (p.v - O.v) * (p.v - O.v));
						d := d - ((q.h - O.h) * (q.h - O.h) + (q.v - O.v) * (q.v - O.v));
						inferieur := (d > 0);
					end
				else
					inferieur := ((determinant(O, p1, p) > 0) or ((determinant(O, p1, p) = 0) and (scalaire(O, p1, p) > 0)));
			end
		else
	{le cas p et q non alignes :}
			begin
				b := ((determinant(O, p1, p) > 0) and (determinant(O, p1, q) > 0));
				b := b or ((determinant(O, p1, p) < 0) and (determinant(O, p1, q) < 0));
				if b then
					begin
						if (determinant(O, p, q) > 0) then
							inferieur := true
						else if (determinant(O, p, q) < 0) then
							inferieur := false
						else
   		{si (determinant(O, p, q) = 0) , p avant q si Op superieur a Oq}
							begin
								d := ((p.h - O.h) * (p.h - O.h) + (p.v - O.v) * (p.v - O.v));
								d := d - ((q.h - O.h) * (q.h - O.h) + (q.v - O.v) * (q.v - O.v));
								inferieur := (d > 0);
							end;
					end;

				if ((determinant(O, p1, p) > 0) and (determinant(O, p1, q) < 0)) then
					begin
						inferieur := true;
					end;
				if ((determinant(O, p1, p) < 0) and (determinant(O, p1, q) > 0)) then
					begin
						inferieur := false;
					end;

		{p sur la demi droite Op1 du meme cote}
				if ((determinant(O, p1, p) = 0) and (scalaire(O, p1, p) > 0)) then
					begin
						inferieur := true;
					end;
		{p sur la  droite Op1 , autre demi droite}
				if ((determinant(O, p1, p) = 0) and (scalaire(O, p1, p) < 0)) then
					begin
						inferieur := (determinant(O, p1, q) < 0);
					end;

		{q sur la demi droite Op1 du meme cote}
				if ((determinant(O, p1, q) = 0) and (scalaire(O, p1, q) > 0)) then
					begin
						inferieur := false;
					end;
		{q sur la  droite Op1 , autre demi droite}
				if ((determinant(O, p1, q) = 0) and (scalaire(O, p1, q) < 0)) then
					begin
						inferieur := (determinant(O, p1, p) > 0);
					end;

			end;
	end;


	procedure echange (var p1, p2: Point);
		var
			x: Point;
	begin
		x := p1;
		p1 := p2;
		p2 := x;
	end;


	procedure tri (var t: EnsemblePoint; n: integer);
{tri par selection, on peux mettre ici un tri meilleur en nlog(n)}
		var
			i, j, min: integer;
	begin
		for i := 1 to n - 1 do
			begin
				min := i;
				for j := i + 1 to n do
					if (inferieur(origine, D, t[j], t[min])) then
						min := j;
				echange(t[i], t[min]);
			end;
	end;


{----------------visualisation du tri selon l'ordre polaire-(optionnel)-------------}
	procedure Trace_ordre_polaire (t: EnsemblePoint; n: integer);
{dessine a chaque clic, et dans l'ordre polaire, les rayons allant de l'origine}
{a chaque point de l'ensemble de points saisis}
		var
			i: integer;
			q: Point;
	begin
		MoveTo(origine.h, origine.v);
		LineTo(D.h, D.v);
		for i := 1 to n do
			begin
				MoveTo(origine.h, origine.v);
				LineTo(t[i].h, t[i].v);
				while not button do
					;
				while button do
					;
				GetMouse(q);
			end;
	end;

{----Listes doublement chainees circulaires  (types donnes en tete du programme)-----}
	procedure inserer_tete (p: Point; var l: ListePoint);
{insertion d'un point p en tete d'une liste circulaire l}
	begin

              {XXXXXXXXXXXXXXX a completer XXXXXXXXXXXXXXXXXXX}

	end;

	procedure supprimer (m: ListePoint);
{on supprime l'element de la liste l pointe par m et on remet la liste circulaire}
{la liste l aura toujours au moins un element}
	begin

              {XXXXXXXXXXXXXXX a completer XXXXXXXXXXXXXXXXXXX}

	end;

	procedure FaireListe (t: EnsemblePoint; var l: ListePoint);
{on cree la liste doublement chainee a partir du tableau de points t}
{les points de la liste sont toujours tries suivant l'ordre polaire}
	begin
		l := nil;
              {XXXXXXXXXXXXXXX a completer XXXXXXXXXXXXXXXXXXX}

	end;

	procedure TraceEnveloppe (l: ListePoint);
{trace le contour de l'enveloppe convexe}
		var
			p: Point;
			debutliste: ListePoint;
	begin
		if l <> nil then
			begin
				debutliste := l;
				p := l^.point;
				MoveTo(p.h, p.v);
				while (l^.succ <> debutliste) do
					begin
						LineTo(l^.succ^.point.h, l^.succ^.point.v);
						l := l^.succ;
					end;
				LineTo(p.h, p.v);
			end;
	end;

{----------------------Graham------------------------------------------}
	function TourGauche (p, q, r: Point): boolean;
	begin

              {XXXXXXXXXXXXXXX a completer XXXXXXXXXXXXXXXXXXX}

	end;


	procedure GrahamTri (var t: EnsemblePoint; n: integer);
		var
			b: boolean;
			min, i: integer;
	begin
		b := calcul_origine(t, origine);
		min := 1;
		for i := 2 to n do
			if t[i].v > t[min].v then
				min := i
			else if (t[i].v = t[min].v) and (t[i].h > t[min].h) then
				min := i;
		D := t[min];
		PaintCircle(D.h, D.v, 4);
		tri(t, n);
	end;


	procedure GrahamScan (l: ListePoint);

	begin

              {XXXXXXXXXXXXXXX a completer XXXXXXXXXXXXXXXXXXX}

	end;



{---------------------------Programme principal--------------------------------}
begin
{Ajouter ici au debut InitQuickDraw; si vous etes sous PC}

	SetRect(r, 10, 50, 600, 400);
	SetDrawingRect(r);
	ShowDrawing;

	n := EntrePoints(t);
	if n > 2 then
		begin
			GrahamTri(t, n);
		   
			Trace_ordre_polaire(t, n);
		   {On peut masquer ceci s'il y a beaucoup de points}
                   {il faut clicker pour dessiner les rayons}
		   
			FaireListe(t, l);
			GrahamScan(l);
			TraceEnveloppe(l);
		end;
end.