หาจำนวนสี่เหลี่ยม (Quadrilaterals) ที่เป็นไปได้จากจุดที่กำหนดด้วย C++

สี่เหลี่ยม (Quadrilateral) เป็นรูปหลายเหลี่ยมที่มี 4 จุดยอดและ 4 ด้านในเรขาคณิตยุคลิด ชื่ออื่นๆ เช่น 4-gon รวมอยู่ในชื่ออื่นๆ ของสี่เหลี่ยม และบางครั้งก็เรียกว่า สี่เหลี่ยมจัตุรัส (square) เป็นต้น

ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนสี่เหลี่ยมที่เป็นไปได้จากจุดที่กำหนด ในโจทย์นี้ เราต้องหาว่าสามารถสร้างสี่เหลี่ยมได้กี่รูปจากจุดที่กำหนด 4 จุด (x, y) บนระนาบเกณฑ์ (Cartesian plane) ตัวอย่าง:

Input : A(-2, 8), B(-2, 0), C(6, -1), D(0, 8) Output : 1 Explanation : สามารถสร้างสี่เหลี่ยมได้ 1 รูป (ABCD)

Input : A(1, 8), B(0, 1), C(4, 0), D(1, 2) Output : 3 Explanation : สามารถสร้างสี่เหลี่ยมได้ 3 รูป (ABCD), (ABDC) และ (ADBC)

วิธีการหาคำตอบ

• เราจะตรวจสอบก่อนว่า 3 ใน 4 จุดเรียงเส้นตรง (collinear) หรือไม่ หากใช่ ไม่สามารถสร้างสี่เหลี่ยมได้จากจุดเหล่านี้

• หลังจากนั้น เราจะตรวจสอบว่ามี 2 ใน 4 จุดที่เหมือนกันหรือไม่ หากใช่ ไม่สามารถสร้างสี่เหลี่ยมได้

• ตอนนี้ เราจะตรวจสอบว่าเส้นทแยงมุม (diagonals) ตัดกันหรือไม่ หากใช่ จะมี สี่เหลี่ยมที่เป็นไปได้เพียง 1 รูป เรียกว่า สี่เหลี่ยม볼록 (convex quadrilateral)

จำนวนจุดตัดทั้งหมด = 1

หากเส้นทแยงมุมไม่ตัดกัน จะมีสี่เหลี่ยมที่เป็นไปได้ 3 รูป เรียกว่า สี่เหลี่ยมอ목 (concave quadrilateral)

จำนวนจุดตัดทั้งหมด = 0

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct Point { // จุด
    int x;
    int y;
};

int check_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;
    return (val > 0) ? 1 : 2;
}

// ตรวจสอบว่าส่วนเส้นตัดกันหรือไม่
bool check_Intersect(Point A, Point B, Point C, Point D) {
    int o1 = check_orientation(A, B, C);
    int o2 = check_orientation(A, B, D);
    int o3 = check_orientation(C, D, A);
    int o4 = check_orientation(C, D, B);
    if (o1 != o2 && o3 != o4)
        return true;
    return false;
}

// ตรวจสอบว่าจุด 2 จุดเหมือนกันหรือไม่
bool check_similar(Point A, Point B) {
    // หากพบจุดเหมือนกัน คืนค่า false หมายถึงไม่สามารถสร้างสี่เหลี่ยมได้
    if (A.x == B.x && A.y == B.y)
        return false;
    // คืนค่า true สำหรับไม่พบจุดเหมือนกัน
    return true;
}

// ตรวจสอบความเรียงเส้นตรงของ 3 จุด
bool check_collinear(Point A, Point B, Point C) {
    int x1 = A.x, y1 = A.y;
    int x2 = B.x, y2 = B.y;
    int x3 = C.x, y3 = C.y;
    if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2))
        return false;
    else
        return true;
}

// ฟังก์ชันหลัก
int main() {
    struct Point A, B, C, D;
    A.x = -2, A.y = 8; // A(-2, 8)
    B.x = -2, B.y = 0; // B(-2, 0)
    C.x = 6, C.y = -1; // C(6, -1)
    D.x = 0, D.y = 8;  // D(0, 8)
    
    // ตรวจสอบว่ามี 3 จุดใดๆ เรียงเส้นตรงหรือไม่
    bool flag = true;
    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 == false) {
        cout << "Number of quadrilaterals possible from the given points: 0";
        return 0;
    }
    
    // ตรวจสอบว่ามี 2 จุดเหมือนกันหรือไม่
    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 == false) {
        cout << "Number of quadrilaterals possible from the given points: 0";
        return 0;
    }
    
    // ตรวจสอบว่าเส้นทแยงมุมตัดกันหรือไม่
    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 == true)
        cout << "Number of quadrilaterals possible from the given points: 3";
    else
        cout << "Number of quadrilaterals possible from the given points: 1";
    
    return 0;
}

ผลลัพธ์

Number of quadrilaterals possible from the given points : 1

คำอธิบายโค้ด

โค้ดนี้สามารถเข้าใจได้ในขั้นตอนต่อไปนี้:

• ตรวจสอบว่ามี 3 จุดใดๆ เรียงเส้นตรงหรือไม่ หากใช่ จำนวนสี่เหลี่ยม: 0

• ตรวจสอบว่ามี 2 จุดเหมือนกันหรือไม่ หากใช่ จำนวนสี่เหลี่ยม: 0

• ตรวจสอบว่าส่วนเส้นตัดกันหรือไม่:

  • หากใช่ จำนวนสี่เหลี่ยม: 1

  • หากไม่ใช่ จำนวนสี่เหลี่ยม: 3

สรุป

ในบทความนี้ เราแก้ปัญหาการหาสี่เหลี่ยมที่เป็นไปได้ทั้งหมดที่สามารถสร้างจาก 4 จุดที่กำหนด เราเข้าใจว่าจำนวนสี่เหลี่ยมขึ้นอยู่กับความเรียงเส้นตรง จุดตัด และการวางตัว เรายังเขียนโปรแกรม C++ สำหรับปัญหานี้ และสามารถเขียนโปรแกรมนี้ในภาษาอื่นๆ เช่น C, Java, และ Python ได้เช่นกัน