Lien du problème : http://poj.org/problem?id=1269

Description :

Nous savons tous qu'une paire de points distincts sur un plan définit une ligne et qu'une paire de lignes sur un plan intersectera de trois manières : 1) aucune intersection car elles sont parallèles, 2) intersection en une ligne car elles se superposent (c'est-à-dire qu'elles sont la même ligne), 3) intersection en un point. Dans ce problème, vous utiliserez vos connaissences algébriques pour créer un programme qui détermine comment et où deux lignes s'intersectent. Votre progarmme lira répétitivement quatre points qui définissent deux lignes dans le plan x-y et déterminera comment et où ces lignes s'intersectent. Tous les nombres nécessaires à ce problème seront raisonnables, disons entre -1000 et 1000.Entrée

La première ligne contient un entier N entre 1 et 10 décrivant combien de paires de lignes sont représentées. Les N lignes suivantes contiendront chacune huit entiers. Ces entiers représentent les coordonnées de quatre points sur le plan dans l'ordre x1y1x2y2x3y3x4y4. Ainsi, chacune de ces lignes d'entrée représente deux lignes sur le plan : la ligne passant par (x1,y1) et (x2,y2) et la ligne passant par (x3,y3) et (x4,y4). Le point (x1,y1) est toujours distinct de (x2,y2). De même pour (x3,y3) et (x4,y4).Sortie

Il devrait y avoir N+2 lignes de sortie. La première ligne de sortie devrait lire "INTERSECTION DES LIGNES". Ensuite, il y aura une ligne de sortie pour chaque paire de lignes planes représentée par une ligne d'entrée, décrivant comment les lignes s'intersectent : aucune, ligne, ou point. Si l'intersection est un point, votre programme devrait afficher les coordonnées x et y du point, correctes à deux décimales. La dernière ligne de sortie devrait lire "FIN DE LA SORTIE".Exemple d'entrée

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

Exemple de sortie

INTERSECTION DES LIGNES
POINT 2.00 2.00
AUCUNE
LIGNE
POINT 2.00 5.00
POINT 1.07 2.20
FIN DE LA SORTIE<br></br>Approche : Ce problème consiste à déterminer la relation positionnelle entre deux lignes. Si elles sont parallèles, on affiche "AUCUNE" ; si elles s'intersectent, on affiche "POINT" et les coordonnées du point d'intersection ; si elles sont confondues, on affiche "LIGNE". Pour déterminer si deux lignes sont parallèles, on vérifie si leurs vecteurs directeurs unitaires sont égaux ou opposés (c'est-à-dire si leurs pentes sont égales). Si c'est le cas, elles sont soit parallèles, soit confondues ; sinon, elles s'intersectent. Dans ce cas, on appelle une fonction pour calculer le point d'intersection. Pour vérifier si les lignes sont confondues, il suffit de vérifier si un point d'une ligne appartient à l'autre ligne.</br><br></br>Implémentation :

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct Point {
 7     double x, y;
 8     Point (double x = 0, double y = 0) : x(x), y(y) {}
 9 };
10 
11 typedef Point Vecteur;
12 
13 int nbCas;
14 Point P1, P2, P3, P4;
15 
16 Vecteur operator + (Vecteur A, Vecteur B) {
17     return Vecteur(A.x + B.x, A.y + B.y);
18 }
19 
20 Vecteur operator - (Vecteur A, Vecteur B) {
21     return Vecteur(A.x - B.x, A.y - B.y);
22 }
23 
24 Vecteur operator * (Vecteur A, double p) {
25     return Vecteur(A.x * p, A.y * p);
26 }
27 
28 bool operator < (const Point& a, const Point& b) {
29     return a.x < b.x || (a.x == b.x && a.y < b.y);
30 }
31 
32 const double epsilon = 1e-10;
33 int Comparaison(double x) {
34     if(fabs(x) < epsilon)
35         return 0;
36     else
37         return x < 0 ? -1 : 1;
38 }
39 
40 bool operator == (const Point& a, const Point& b) {
41     return Comparaison(a.x - b.x) == 0 && Comparaison(a.y - b.y) == 0;
42 }
43 
44 double ProduitScalaire(Vecteur A, Vecteur B) {
45     return A.x * B.x + A.y * B.y;
46 }
47 
48 double Norme(Vecteur A) {
49     return sqrt(ProduitScalaire(A, A));
50 }
51 
52 double ProduitVectoriel(Vecteur A, Vecteur B) {
53     return A.x * B.y - A.y * B.x;
54 }
55 
56 // Calcul du vecteur directeur unitaire
57 Vecteur VecteurUnitaire(Vecteur w) {
58     return Vecteur(w.x / Norme(w), w.y / Norme(w));
59 }
60 
61 // Vérifie si deux lignes ne s'intersectent pas
62 bool EstParallele(Vecteur A, Vecteur B) {
63     return VecteurUnitaire(A) == VecteurUnitaire(B) || VecteurUnitaire(Vecteur(- A.x, - A.y)) == VecteurUnitaire(B);
64 }
65 
66 Point PointIntersection(Point P, Vecteur v, Point Q, Vecteur w) {
67     Vecteur u = P - Q;
68     double t = ProduitVectoriel (w, u) / ProduitVectoriel(v, w);
69     return P + v * t;
70 }
71 
72 // Vérifie si deux lignes sont confondues en vérifiant si elles ont un point commun
73 bool AppartientALigne(Point p, Point a1, Point a2) {
74     return Comparaison(ProduitVectoriel(a1 - p, a2 - p)) == 0;
75 }
76 
77 
78 int main() {
79     while(~scanf("%d", &nbCas)) {
80         printf("INTERSECTION DES LIGNES\n");
81         while(nbCas--) {
82             scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &P1.x, &P1.y, &P2.x, &P2.y, &P3.x, &P3.y, &P4.x, &P4.y);
83             if(EstParallele(P1 - P2, P3 - P4)) {
84                 if(AppartientALigne(P1, P3, P4)) {
85                     printf("LIGNE\n");
86                 } else {
87                     printf("AUCUNE\n");
88                 }
89             } else {
90                 Point Intersection = PointIntersection(P1, P1 - P2, P3, P3 - P4);
91                 printf("POINT %.2f %.2f\n", Intersection.x, Intersection.y);
92             }
93         }
94         printf("FIN DE LA SORTIE\n");
95     }
96 }