Centrale Informatique MP 2005

Thème de l'épreuve Composantes connexes de polygones simples. Complexité de communication.
Principaux outils utilisés espaces affines, arbres binaires, représentation binaire, complexité

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


 

% e......___... ...30_Ëämo...z_ ä.ä...

mêw ooeäQ:OE - ÆOEÈOEO mÈQË©Q

Partie I - Polygones simples

Dans toute cette partie, le plan est muni d'un repère orthonormé fixé. On iden-
tifiera un vecteur et le couple de ses coordonnées dans ce repère.

Notes de programmation. On dispose des types point , vecteur , segment
et polygone . Un point (ou un vecteur) est défini par deux entiers, un seg--
ment est défini par deux points et un polygone est une liste de points.

Remarque : dans tout le problème un segment, resp. un polygone, est toujours
supposé formé de points distincts.

En Caml :

type point = { x:int ; y:int };;

type vecteur = { xv:int ;.yv:int };;

type segment { a:point ; b:point };;

type polygon == point list;;

On dispose par ailleurs de constructeurs de vecteurs et de segments à partir
des points les définissant ;

let CreerVecteur p q = { xv = q.x--p.x ; yv = q.y--p.y};;
let CreerSegment p q = { a = p ; b = q };;

Les fonctions dont on demandera le code devront avoir pour signatures :
determinant : vecteur --> vecteur --> int = 
produit_scalaire : vecteur --> vecteur --> int = 
direct : point --> point --> point --> int = 

meme_cote : segment --> point --> point --> int = 
appartient : segment --> point --> int = 

intersecte : segment --> segment -> int = 

simplifie : polygone --> polygone = 

en_dehors : polygone --> point = 

interieur : polygone --> point --> int = 

Pour simplifier la présentation Caml/ Pascal, la notation fonctionnelle
f (u,v) est utilisée dans l'énoncé à la place de f u v en Caml.

En Pascal :

type
point=record x,y:integer end;
vecteur=record xv,yv: integer end;

segment=record a,b:point end;

polygone="cellule;

cellule=record contenu:point; suivant:polygone end;
Les fonctions/procédures dont on demandera le code auront pour entêtes :
function determinant(u,v:vecteur):integer;
function produit_scalaire(u,vzvecteur):integer;
function direct(a,b,c:point):integer;
function meme_cote(I:segment;p,q:point):integer;
function appartient(I:segment; p:point):integer;
function intersecte(l,stegment):integer;
function simplifie (P:polygone):polygone;
procedure en_dehors(P:polygone; var res:point);
function interieur(P:polygone;ptzpoint):integer;

I.A - Intersection

Remarque : géométriquement, le segment [a, b] est l'ensemble des points de la

droite (a, b) situés entre a et b ; on rappelle que les segments considérés sont
non réduits à un point.

I.A.1) Écrire des fonctions determinant et produit_scalaire telles que
determinant ( u , v) retourne le déterminant de la matrice formée par les vec--

teurs u et v, et produit_scalaire ( u,v) retourne le produit scalaire des vec--
teurs u et v.

I...A2) Définition: étant donne'_)s t_rpis points a, b, c, le triangle (a, b, 
c) est

direct si une mesure_gie _l_} angle (ab, ac) est dans l'intervalle ]O, n[, 
indirect si une
mesure de l' angle (ab, ac) est dans l'intervalle ]--n, 0[ , aplati si les 
trois points a,

b et c sont alignés.

. . o . H __>
Montrer que le triangle (a, b, c) est d1rect s1 et seulement s1 det(ab, ac) > 0 
.

I.A.3) Écrire une fonction direct telle que direct(a,b,c) retourne 1 si
le triangle (a, b, c) est direct, --1 s'il est indirect et 0 s'il est ap1ati.

I.A.4) Écrire une fonction meme_cote telle que meme_cote(I , p , q) retourne
1 si les points p et q sont du même côté de la droite D portée par le segment I 
,
--1 s'ils ne sont pas du même côté, et 0 si p ou q est sur D.

Illustrer la démarche à l'aide de figures bien choisies.

I.A.5) Écrire, en la justifiant, une fonction appartient telle que appar--
tient(I,p) retourne 1 si le point p appartient au segment I et --1 sinon.

I.A.6) Écrire une fonction intersecte telle que intersecte ( I , J )
retourne 1 si les segments I et J ont une intersection non vide et --1 sinon.

Utiliser et justifier & l'aide de figures le fait que, sauf cas particuliers à 
expliciter;
I et J ont une intersection non vide lor3que les extrémités de 1 ne sont pas du

même côté de J et que conjointement les extrémités de J ne sont pas du même
côté de I .

LB - Intérieur / Extérieur

Dans_cette partie, n est un entier strictement supérieur à 2 , P : p1p2... pn 
est
un polygone ; les points pl,..., pn sont les sommets du polygone ; les segments

[p1, p2], [pn_ 1, pn], [pn, pl] en sont les arêtes. Par convention on pose po : 
pn
et pi+ ,... : pi pour tout entier naturel le .

Géométriquemeht, un polygone est, par définition, l'ensemble des points de ses
arêtes ; ainsi on dit qu'un point a est sur le polygone P s'il appartient à 
l'une de

ses arêtes. On dit qu'un segment S coupe le polygone P si ce segment à une
intersection non vide avec l'une des arêtes de P.

De plus, dans ce problème, le polygone P sera toujours supposé simple, ce qui
signifie que deux arêtes quelconques non consécutives sont toujours disjointes
et que deux arêtes consécutives ont un seul point commun.

Résultat admis l. Un polygone simple P sépare le plan en deux composan-
tes connexes, ce qui signifie que le complémentaire de P dans le plan com-
porte deux composantes connexes: l'intérieur de P est par définition la
composante connexe bornée et l'autre, non bornée, est l'extérieur de P.

Résultat admis 2. Soient P un polygone simple, a et b deux points du plan

qui ne sont pas sur P. Si le segment [a, b] ne coupe pas P alors a et b sont
dans la même composante connexe.

Résultat admis 3.Soient P un polygone simple, a et b deux points du plan
qui ne sont pas sur P. Si le segment [a, b] coupe P en un seul point qui n'est

pas un sommet de P, alors a et b ne sont pas dans la même composante
connexe.

I.B.l) Écrire une fonction simplifie telle que simplifie ( P) supprime du
polygone P les points p,- tels que pi_1, pi, pi+1 sont alignés. Évaluer sa com-
plexité. '
Dans la suite, le polygone P sera supposé sous sa forme simplifiée, i.e. il 
n'existe
pas de sommet Pi tel que pi_1, pi, pi+1 sont alignés.

I.B.2) Caml : écrire une fonction en_dehors telle que en_dehors P
retourne un point appartenant àla composante extérieure de P . Le temps d'exé-
cution (dans le pire des cas) doit être linéaire en le nombre de points de P.

Pascal: écrire une procédure en_dehors telle que en_dehors(P,pt) place
dans la variable pt un point appartenant à la composante extérieure de P. Le

temps d'exécution (dans le pire des cas) doit être linéaire en le nombre de 
points
de P.

I.B.3) Soit 3 un point à l'extérieur de P. En supposant que le segment [q, 8]
ne contient aucun des sommets de P , dire dans quelle composante connexe se
situe q , en fonction du nombre d'intersections de [q, 8] avec P.

I.B.4) En déduire une fonction interieur telle que interieur ( P , q) ren-
voie 1 si q est dans la composante intérieure de P, --1 si q est dans la compo--
sante extérieure, et 0 si q est sur P. Le nombre d'opérations (dans le pire des
cas) de la fonction doit être linéaire en le nombre de sommets de P.

On fera ici l'hypothèse que le point s à l'extérieur de P est tel qu'aucun 
sommet
de P n'est sur le segment [q, 3].

I.B.5) Adapter cette fonction pour traiter tous les cas d'intersections possi-
bles et donner alors le nombre d'opérations (dans le pire des cas).
Indication : on déplacera habilement le point extérieur 3 .

I.B.6) Soient deux points a et b qui ne sont pas sur P et tels que [a, b] coupe
P en un seul point qui est l'un de ses sommets pi . Caractériser, par une condi-
tion portant sur p,-_1 , p,- +1 et [a, b] , l'appartenance des points a et b à 
la même
composante connexe. Justifier à l'aide de figures bien choisies.

I.B.7 ) Soient deux points a et b qui ne sont pas sur P et tels que l'intersec-
tion de [a, b] et de P est une arête [p,-, pi +1] de P. Caractériser, par une 
condi-
tion portant sur p,-_1 , p,- +2 et [a, b] , l'appartenance des points a et b à 
la même
composante connexe. Justifier & l'aide de figures bien choisies.

I.B.8) Réécrire la fonction interieur de la question I.B.5 avec un nombre
d'opérations (dans le pire des cas) linéaire par rapport à n .

Partie II - Complexité de communication

Lorsque E est un ensemble fini, lEI désigne son cardinal. Lorsque x est un réel,
Fx] (resp. Lx]) désigne sa partie entière supérieure (resp. inférieure), 
c'est-à-
dire l'unique entier vérifiant x 5 Fx] < x + 1 (resp. x -- 1 < Lx] 5 x ).

Soit une application f : X >< Y --> Z . Pour y E Y fixé, f y désigne 
l'application par--

tielle fy { X_>Z
xr---->f(x,y)

et pour x E X fiXé, f x l'application partielle fx { Y _' Z

y+-->f(x,y)

II.A - Communication à sens unique

Dans cette partie on modélise le scénario suivant. Soient X , Y et Z trois 
ensem-
bles finis arbitraires et f : X x Y --> Z une fonction donnée. Deux personnes, 
Alice
et Bob, veulent calculer f (x, y) pour des valeurs x E X et y E Y . La 
difficulté est
que seule Alice connaît x et seul Bob connaît y. L'objectif est de déterminer
l'information minimale qu'Alice doit envoyer à Bob pour que ce dernier puisse
calculer f(x, y).

Un protocole à sens unique 95 calculant f est un couple de fonctions (go, g,) ,
avec go : X-->{O,1}* et g1 : {0,1}* x Y ---> Z , tel que EUR1(go(x)»y) : f(x, 
y) , pour tout
x E X et y & Y , {0,1}* désignant l'ensemble des mots sur l'alphabet {0,1}.

Autrement dit, g0(x) est l'information qu'Alice envoie à Bob, et gl(m, y) est la
valeur calculée par Bob ayant reçu le message m d'Alice.

Le coût sur l'entrée (x, y) d'un protocole à sens unique @ est la taille en 
bits de
g0(x) , c'est--à-dire la longueur de ce mot. Le coût d'un protocole à sens 
unique est
le maximum de ses coûts sur toutes les entrées possibles. La complexité de com-

. . \ . , 1 . . ,\
munzcatzon a sens unzque de f, notee D (f) , est le m1n1mum des couts des pro-
tocoles à sens unique calculant f.

Note sur la rédaction. Dans cette partie, la description d'un protocole se fera
par la donnée explicite des fonctions go et g1 correspondantes.

II.A.1) Exemples - Propriétés simples
a) Calculer D'(f ) lorsque f est une fonction constante.

b) Trouver, pour f donnée, un protocole dont le coût est [log2lel. Que peut- on
en déduire sur D (f)?

c) Soient X_ -- {1,.. n,} p un entier tel que 15 p sn--1, et f une fonction de
période p par rapport à la première variable, i. e. f (x + p, y)= f (x y) pour 
tout
(x,y) EX x Y tel que x +p s n. Montrer que D (f) 5 Flogpl .

d) X et Y sont ici l'ensemble des parties de {1,.. .,n}, et, pour x, yC{1,... 
.,n},

f(x, y) est le plus grand élément de x U y. Montrer que D (f) < {log2nl. Compa-
rer àla majoration de la question II. A. 1-- b.

e) Montrer que pour chaque yEY fixé, Dl(f)zllog2llm(fy)ll, avec Im(fy)
l'ensemble des valeurs prises par f y .

f) Calculer D1(f ) , f désignant la fonction de la question II.A.l-d.
II.A.2) Calcul exact de Dl(f)

On suppose que X : {1,...,p} et Y : {1,...,q}, pour deux entiers p et q stricte-
ment positifs. La matrice de communication de f : X >< Y --a Z est un tableau à 
p

lignes et q colonnes, noté M f , dont les lignes sont indexées par X et les 
colonnes

par Y, et définie par (M f) _ f--(x, y), pour x EX et y E Y. Soit t le nombre de
lignes distinctes de M f Orly va montrer l'égalité D (f)_ -- {log2tl.

a) Donner un protocole calculant f dont le coût est {log2tl .

b) Montrer que le protocole précédent est optimal, i.e. tout protocole calculant
f a un coût supérieur ou égal à { log2tl .

c) Application :Alice et Bob détiennent chacun un mot de taille n sur l'alphabet
{0,1}. Quelle information minimale Alice doit--elle fournir à Bob pour que 
celui-
ci puisse décider de façon certaine si les deux mots sont égaux ?

On commencera par modéliser précisément cette situation en terme de protocole
de communication à sens unique.

Donner un protocole à sens unique dont le coût atteint cette borne.

Lorsque X et Y sont quelconques, l'égalité D'(f) : [log2tl est maintenue en pre-
nant pour t le nombre d'applications partielles ( fx)x & X distinctes. En 
effet, cha-
que fonction f x correspond à une ligne de la matrice dans le cas précédent.

II.B - Communication avec aller-retour

Nous considérons maintenant des communications générales où les deux parti-
cipants peuvent'interagir plusieurs fois entre eux. De plus, ils veulent mainte-
nant calculer tous les deux la valeur de la fonction. Soient X , Y et Z trois
ensembles finis arbitraires et f : X x Y --> Z une fonction donnée. Étant donnés
x E X , détenu par Alice et y & Y , détenu par Bob, le but est de calculer f 
(x, y) en
s'échangeant le minimum de bits. Un protocole (calculant f) est maintenant
divisé en étapes. À chaque étape, le protocole désigne une personne, indifférem-
ment Alice ou Bob. La personne désignée envoie alors un bit à l'autre personne.
Ce bit ne dépend que des bits échangés précédemment et de l'entrée détenue par
la personne désignée. Lorsque le protocole termine, alors les deux participants
sont en mesure de calculer f (x y) d' après les bits échangés et la valeur de x 
(res-
pectivement y).

Plus formellement : un protocole 95 de domaine X x Y et à valeurs dans 2 est
un arbre binaire étiqueté comme suit. Chaque noeud interne est étiqueté soit
« Alice » soit « Bob », chaque feuille est étiquetée par un élément 2 EUR Z , 
et enfin
les arêtes par des sous-ensembles de X ou de Y avec la contrainte suivante. Si
un noeud interne est étiqueté « Alice » (respectivement « Bob ») alors ses 
arêtes
gauche et droite sont respectivement étiquetées par des sous-ensembles dis-
joints E g et Ed de X (respectivement de Y).

La valeur du protocole 95 sur l'entrée (x, y) , avec x E X et y E Y , est 
l'étiquette
de la feuille atteinte en partant de la racine et en parcourant l'arbre suivant 
le
chemin décrit ci-après. A chaque noeud interne étiqueté « Alice » (respective-
ment « Bob ») le parcours suit le fils gauche si x E E g (respectivement y E E 
g ) et

le fils droit dans l'autre cas, i.e. x E E d (respectivement y EUR Ed ). Pour 
indiquer
le sens du parcours, Alice (respectivement Bob) envoie à Bob (respectivement
Alice) le bit 0 pour le fils gauche et 1 pour le fils droit. Le protocole sera 
toujours
supposé bien défini de sorte qu'à chaque noeud, x ou y selon le cas, appartient
àla réunion Eg U Ed .

Le coût sur l'entrée (x, y) d'un protocole ? est la longueur totale du chemin 
sur
l'entrée (x, y) , soit donc la profondeur de la feuille atteinte.

Le coût d'un protocole est le maximum de ses coûts sur toutes les entrées possi-
bles, soit encore la hauteur de l'arbre @ .

Un protocole calcule f si sa valeur est f (x, y) sur chaque entrée (x, y) .

La complexité de communication de f , notée D(f ) , est le minimum des coûts des
protocoles calculant f.

Note sur la rédaction. Dans cette partie, les protocoles seront souvent décrits
sous forme compacte où chaque série de bits émis consécutivement par le même
participant est concentré sur la même ligne.

Exemple. Soient X : {0,1}3, Y = {l, 2, 3} et Z = {0,1}. Posons
f ((x1, x2, x3), y) = x y . Suivent un protocole pour f ainsi que sa forme 
compacte.

1.Siy
2.Sib

1 Bob envoie àAlice le bit b = 0 sinon le bit b = 1 .
0 alors Alice renvoie x1 à Bob

et le protocole termine et renvoie f (x, y) = x1 .
3. Si y = 2 Bob envoie àAlice le bit c = O , sinon le bit c = 1.
4. Alice envoie le bit x2 +0 à Bob.
5. Le protocole termine et renvoie f (x, y) = x2 % .

Figure 2 : Forme compacte du protocole pour f .

ll.B.1) Quelques exemples
a) Voici la forme compacte d'un protocole où X : Y : Z = {O, 1, 2, 3}.

1.Alice calcule a = 0 si xEUR{0,1}, et a = 1 sinon.
Alice envoie a à Bob.

2. Si a = 0 et yEUR{2, 3} Bob renvoie b = 1.
Si a = 0 et yEUR{0,1} Bob renvoie b = 0.
Si a = 1 et yE{O,1} Bob renvoie b = 1.

Sia : 1 et yE{2, 3} Bob renvoie b = O.

8. Si b = 1 le protocole termine et renvoie f(x, y) : 1----a.
Sinon Alice renvoie c = x -- 2a .

4. Bob renvoie d = 1 si c J + 1 s D(f) s D'
			

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP 2005 -- Corrigé
Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par 
JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Le sujet est composé de deux problèmes distincts. Il est relativement long et 
comporte quelques questions difficiles, en particulier les dernières de chaque 
partie. Peu de
connaissances sont requises : seules quelques propriétés classiques sur les 
espaces
affines, les arbres et la représentation binaire d'entiers sont nécessaires.
Le premier problème amène à trouver un algorithme permettant de déterminer
si un point est à l'intérieur ou à l'extérieur d'un polygone simple ; cet 
algorithme
est linéaire en le nombre de points du polygone. L'énoncé ne demande pas de 
démonstrations formelles de la plupart des propriétés géométriques mais 
seulement des
justifications à l'aide de figures ; il fait donc surtout appel à des « 
intuitions géométriques ». Des questions de programmation introduisent 
progressivement les fonctions
qui seront nécessaires à l'implémentation de l'algorithme. Les fonctions des 
deux dernières questions sont longues à rédiger.
Le second problème propose de mener une étude de la complexité de 
communication. Deux personnes doivent coopérer pour calculer une fonction dont 
chacun
connaît une partie de l'entrée. Dans la première partie du sujet, on suppose 
que seul
un acteur peut communiquer de l'information à l'autre et on cherche à trouver la
quantité minimale d'information qui doit être transmise pour que les deux 
puissent
calculer la fonction. Ensuite, le modèle est élargi au cas où les deux acteurs 
peuvent
s'échanger de l'information et on compare la quantité minimale d'information qui
doit être transmise avec celle du premier modèle. Ce problème fait manipuler le 
codage des entiers en binaire et les formules classiques permettant de 
déterminer le
nombre de chiffres d'un tel codage, ainsi que les arbres binaires. Il demande 
un peu
d'intuition.

Indications
I.A.2 Effectuer un changement de base orthonormale dans une base dont l'un des

-
vecteurs est colinéaire à ab et exprimer le déterminant dans cette base.
I.A.4 Les triangles (a, b, p) et (a, b, q) sont-ils directs, indirects ou 
aplatis ?

|-
I.A.5 Distinguer deux cas suivant la valeur du produit scalaire h-
ap
abi lorsque les

-

-
-

-

vecteurs ap et ab sont colinéaires en exprimant ap en fonction de ab.
I.B.1 « Enlever » les points pi du polygone tels que direct pi-1 pi pi+1 
renvoie 0.
I.B.2 Renvoyer un point s dont l'abscisse est plus grande que celle de tous les
sommets de P.
I.B.3 Distinguer suivant la parité du nombre d'intersections de [q, s] et P.
I.B.4 Utiliser la fonction intersecte pour trouver le nombre d'intersections de 
P
avec [q, s] (où s est un point à l'extérieur de P obtenu grâce à en_dehors)
et appliquer le résultat de la question précédente.
I.B.5 Choisir s à l'extérieur de P dont l'ordonnée est égale à l'ordonnée de q
augmentée de 1.
I.B.6 Regarder si pi-1 et pi+1 sont du même côté de [a, b].
I.B.7 Regarder si pi-1 et pi+2 sont du même côté de [a, b].
I.B.8 Utiliser les résultats des deux questions précédentes pour traiter les 
cas où
l'intersection est un sommet de P. Il pourra être utile de convertir P en un
vecteur de points et d'utiliser un modulo pour accéder à ces points.
II.A.1.a Il n'y a pas besoin d'échanger d'information.
II.A.1.b Proposer un protocole tel que g0 (x) envoie le codage binaire de i si 
x est le
i-ème élément de X.
II.A.1.c Envoyer le codage binaire de x mod p.
II.A.1.d Proposer un protocole tel que g0 (x) envoie le codage binaire de Sup 
(x).
II.A.1.e Raisonner par l'absurde et montrer que l'image de f serait plus petite 
qu'elle
ne l'est si l'inégalité n'était pas vérifiée.
II.A.1.f Utiliser la question précédente pour y = .
II.A.2.a Transmettre l'indice de la ligne de la matrice correspondant à x.
II.A.2.b Raisonner de même qu'à la question II.A.1.e.
II.B.1.a Commencer par écrire Mf pour deviner f .
II.B.1.b Alice doit envoyer à Bob le codage binaire de y.
II.B.2.a Proposer un protocole aller-retour, fondé sur celui à sens unique, 
dont le
coût est majoré par D1 (f ) + log2 | Im (f )|.
II.B.2.b Raisonner de même qu'à la question II.A.1.e. Choisir f0 de telle sorte 
qu'il
ne dépende pas de x.
II.B.2.c Proposer un protocole à sens unique qui transmet tous les branchements
qu'Alice ferait dans le protocole aller-retour.
II.B.2.d Représenter f sous forme de matrice pour pouvoir utiliser les 
résultats de la
partie II.A.2, puis utiliser l'inégalité de la question II.B.2.b.

I.

Polygones simples

Les noms CreerVecteur et CreerSegment des fonctions proposées commencent par 
des majuscules, ce qui est déconseillé en caml-light (et interdit
en OCaml). Pour cette raison, nous les avons renommées respectivement en
creer_vecteur et creer_segment dans le corrigé. De même, nous utiliserons
i et non I comme nom de variable pour les segments.

x
x
et
, le
y
y
déterminant de la matrice formée par ces vecteurs est donné par la formule
I.A.1 Si u et v sont des vecteurs de coordonnées respectives

x
y

x
= x · y  - y · x
y

et leur produit scalaire par
hu | vi = x · x + y · y 
Les fonctions demandées s'écrivent donc
let determinant u v =
u.xv * v.yv - u.yv * v.xv
;;
et
let produit_scalaire u v =
u.xv * v.xv + u.yv * v.yv
;;
 
-
I.A.2 Notons  l'angle (ab, -
ac). Par hypothèse (d'après la remarque en introduction
de l'énoncé), les points a et b sont distincts. Il existe donc une base 
orthonormale
B = (u0 , v0 ), de même orientation (directe ou indirecte) que la base 
initiale, avec u0

-

-
colinéaire à!ab et dans le même sens. Dans cette
! base, les coordonnées du vecteur ab

-

k-
ack cos()

sont kabk et celles de -
ac sont
(ce sont les projections du vecteur sur

k-
ack sin()
0
 
-
les axes), et le déterminant de la matrice formée par les vecteurs est kabk·k-
ack·sin().
Notons M la matrice formée par les vecteurs exprimés dans la base initiale, M la
matrice formée par les vecteurs exprimés dans la base B et U la matrice de 
changement de base de la base initiale (qui est par hypothèse orthonormée) à la 
base B.
La matrice U est une matrice de changement de base entre deux bases 
orthonormales,
elle est donc orthogonale et son déterminant est égal à 1. Ainsi

-

det(M) = det(U · M ) = det(U) · det(M ) = det(M ) = kabk · k-
ack · sin()
Ce déterminant est donc strictement positif si et seulement si une mesure de
 
-
l'angle  = (ab, -
ac) est dans l'intervalle ]0, [.
 
-
Le triangle (a, b, c) est direct si et seulement si det(ab, -
ac) > 0.

-

La formule det(M) = kabk · k-
ack · sin() est classique et pouvait être
utilisée sans être redémontrée.
Le déterminant de la matrice formée de n vecteurs dans un espace vectoriel de 
dimension n est appelé produit mixte. D'après une propriété classique,
ce dernier est indépendant du choix de la base orthonormée directe dans 
laquelle sont exprimés les vecteurs (ce que nous avons redémontré dans le cas
particulier où n = 2).
I.A.3 D'après la question précédente, le triangle (a, b, c) est direct si et 
seulement
 
-
 
-
si det(ab, -
ac) > 0. Symétriquement, il est indirect lorsque det(ab, -
ac) < 0 ; et il est
 -
-

-

-
aplati quand det(ab, ac) = 0 (les vecteurs ab et ac sont alors colinéaires).
On en déduit la fonction direct :
let direct a b c =
let d = determinant (creer_vecteur a b) (creer_vecteur a c) in
if d > 0 then 1
else if d < 0 then -1
else 0
;;
Il faut penser à utiliser tant que faire se peut la construction let ... in
afin d'éviter de calculer plusieurs fois le résultat d'une fonction sur les 
mêmes
arguments (ici, le déterminant).
I.A.4 Deux point p et q sont du même côté d'une droite D portée par un segment
I = [a, b] si et seulement si les triangles (a, b, p) et (a, b, q) sont soit 
tous les deux
directs soit tous les deux indirects :
q
q
a
b
a

p

b

p
a

b

p
q
Si l'un des triangles est aplati alors le sommet p ou q correspondant est sur 
la droite
D qui porte [a, b]. La fonction demandée est donc
let meme_cote i p q =
match (direct i.a i.b p), (direct i.a i.b q) with
| 0, _ -> 0
| _, 0 -> 0
| 1, 1 -> 1
| -1, -1 -> 1
| _, _ -> -1
;;
La fonction demandée pouvait être écrite de façon plus concise mais moins
claire en :
let meme_cote i p q =
(direct i.a i.b p) * (direct i.a i.b q)
;;