Kiểm tra hai đường thẳng cắt nhau bằng kiểm tra trên/dưới trong C++

Sử dụng phép thử "trên/dưới" (above-below test) để kiểm tra hai đoạn thẳng có cắt nhau. Đoạn thẳng cắt đường thẳng nếu một đầu nằm bên trái, đầu kia bên phải đường thẳng đó.

Thuật toán

Bắt đầu
  Tạo ngẫu nhiên phương trình đường thẳng 1: A1*x + B1*y + C1 = 0
  Tạo ngẫu nhiên phương trình đường thẳng 2: A2*x + B2*y + C2 = 0
  Tính Y1 = A1*p1 + B1*q1 + C1 (giá trị tại đầu 1 của đoạn 2)
  Nếu Y1 < 0:
     Tính Y2 = A1*p2 + B1*q2 + C1
     Nếu Y2 >= 0 -> cắt nhau, ngược lại -> không cắt
  Ngược lại nếu Y1 > 0:
     Tính Y2
     Nếu Y2 <= 0 -> cắt nhau, ngược lại -> không cắt
  Nếu Y1 == 0 -> điểm nằm trên đường thẳng
Kết thúc

Ví dụ minh họa

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    int x1 = rand()%19+2, y1 = rand()%19+2;
    int x2 = rand()%19+2, y2 = rand()%19+2;
    int p1 = rand()%19+2, q1 = rand()%19+2;
    int p2 = rand()%19+2, q2 = rand()%19+2;

    cout << "Duong thang 1: (" << y2-y1 << ")x+(" << x1-x2 << ")y+(" << x2*y1-x1*y2 << ") = 0" << endl;
    cout << "Duong thang 2: (" << q2-q1 << ")x+(" << p1-p2 << ")y+(" << p2*q1-p1*q2 << ") = 0" << endl;

    int Y1 = (y2-y1)*p1 + (x1-x2)*q1 + (x2*y1-x1*y2);
    if (Y1 < 0) {
        int Y2 = (y2-y1)*p2 + (x1-x2)*q2 + (x2*y1-x1*y2);
        if (Y2 >= 0) cout << "Hai duong cat nhau";
        else cout << "Hai duong KHONG cat nhau";
    } else if (Y1 > 0) {
        int Y2 = (y2-y1)*p2 + (x1-x2)*q2 + (x2*y1-x1*y2);
        if (Y2 <= 0) cout << "Hai duong cat nhau";
        else cout << "Hai duong KHONG cat nhau";
    } else cout << "Diem nam tren duong thang";
    return 0;
}

Kết quả (ví dụ)

Duong thang 1: (-3)x+(2)y+(1) = 0
Duong thang 2: (-5)x+(-5)y+(130) = 0
Hai duong cat nhau