Tìm số tứ giác có thể tạo từ 4 điểm cho trước bằng C++

Cho 4 điểm A, B, C, D trên mặt phẳng Descartes, đếm số tứ giác khác nhau có thể tạo thành. Tứ giác là đa giác 4 đỉnh, 4 cạnh.

Phân tích hình học

• Nếu 3/4 điểm thẳng hàng → 0 tứ giác.
• Nếu có 2 điểm trùng nhau → 0 tứ giác.
• Nếu 2 đường chéo cắt nhau → 1 tứ giác lồi (convex).
• Nếu 2 đường chéo không cắt nhau → 3 tứ giác lõm (concave).

Ví dụ

Input: A(-2,8), B(-2,0), C(6,-1), D(0,8) Output: 1 (tứ giác lồi ABCD)
Input: A(1,8), B(0,1), C(4,0), D(1,2) Output: 3 (ABCD, ABDC, ADBC)

Mã nguồn C++

#include <iostream>
using namespace std;

struct Point { int x, y; };

int orientation(Point i, Point j, Point k) {
    int val = (j.y - i.y) * (k.x - j.x) - (j.x - i.x) * (k.y - j.y);
    if (val == 0) return 0; // thẳng hàng
    return (val > 0) ? 1 : 2; // chiều kim đồng hồ / ngược
}

bool check_Intersect(Point A, Point B, Point C, Point D) {
    int o1 = orientation(A, B, C);
    int o2 = orientation(A, B, D);
    int o3 = orientation(C, D, A);
    int o4 = orientation(C, D, B);
    return (o1 != o2 && o3 != o4);
}

bool check_similar(Point A, Point B) {
    return !(A.x == B.x && A.y == B.y);
}

bool check_collinear(Point A, Point B, Point C) {
    return (C.y - B.y) * (B.x - A.x) != (B.y - A.y) * (C.x - B.x);
}

int main() {
    Point A = {-2, 8}, B = {-2, 0}, C = {6, -1}, D = {0, 8};
    bool flag = true;

    // Kiểm tra 3 điểm thẳng hàng
    flag = flag & check_collinear(A, B, C);
    flag = flag & check_collinear(A, B, D);
    flag = flag & check_collinear(A, C, D);
    flag = flag & check_collinear(B, C, D);
    if (!flag) { cout << "Số tứ giác: 0"; return 0; }

    // Kiểm tra điểm trùng
    bool same = true;
    same = same & check_similar(A, B);
    same = same & check_similar(A, C);
    same = same & check_similar(B, D);
    same = same & check_similar(C, D);
    same = same & check_similar(A, D);
    same = same & check_similar(B, C);
    if (!same) { cout << "Số tứ giác: 0"; return 0; }

    // Kiểm tra đường chéo cắt nhau
    flag = true;
    if (check_Intersect(A, B, C, D)) flag = false;
    if (check_Intersect(A, C, B, D)) flag = false;
    if (check_Intersect(A, B, D, C)) flag = false;

    if (flag) cout << "Số tứ giác: 3";
    else cout << "Số tứ giác: 1";
    return 0;
}

Kết quả

Số tứ giác: 1

Giải thích

1. Kiểm tra 3 điểm thẳng hàng bằng tích có hướng (cross product).
2. Kiểm tra điểm trùng bằng so sánh tọa độ.
3. Kiểm tra đường chéo cắt nhau: hai đoạn AB và CD cắt nhau nếu orientation(A,B,C) != orientation(A,B,D) và orientation(C,D,A) != orientation(C,D,B).
4. Nếu có cặp đường chéo cắt nhau → 1 tứ giác lồi. Ngược lại → 3 tứ giác lõm.

Kết luận

Bài viết giải quyết bài toán đếm tứ giác từ 4 điểm dựa trên hình học giải tích. Mã C++ kiểm tra thẳng hàng, trùng điểm, giao đường chéo. Có thể triển khai bằng C, Java, Python.