หาจำนวนรูปสี่เหลี่ยมที่เป็นไปได้จากจุดที่กำหนดโดยใช้ C++

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

ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนรูปสี่เหลี่ยมที่เป็นไปได้จากจุดที่กำหนด ในปัญหานี้ เราต้องหาว่ารูปสี่เหลี่ยมที่เป็นไปได้มากเท่าใดที่จะสร้างด้วยจุดสี่จุด ( x, y ) ที่ให้ไว้ในระนาบคาร์ทีเซียน นี่คือตัวอย่างสำหรับปัญหาที่กำหนด -

Input : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 )
Output : 1
Explanation : One quadrilateral can be formed ( ABCD )

Input : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 )
Output : 3
Explanation : 3 quadrilaterals can be formed (ABCD), (ABDC) and (ADBC).

แนวทางในการหาแนวทางแก้ไข

• ก่อนอื่นเราจะตรวจสอบว่าจุด 3 ใน 4 อยู่ในแนวเดียวกันหรือไม่ และถ้าใช่ ไม่มีจุดรูปสี่เหลี่ยมใดๆ ที่สามารถเกิดขึ้นได้ .

• หลังจากนั้นเราจะตรวจสอบว่าจุด 2 ใน 4 จุดใดเหมือนกันหรือไม่ และถ้าใช่ จะไม่มีรูปสี่เหลี่ยมใดๆ เกิดขึ้นได้ .

• ตอนนี้เราจะตรวจสอบว่าเส้นทแยงมุมตัดกันหรือไม่ ถ้าใช่ แสดงว่ามีรูปสี่เหลี่ยมด้านเท่าที่เป็นไปได้เพียงรูปเดียวที่สร้างขึ้นได้ เรียกว่า รูปสี่เหลี่ยมนูน .

จำนวนทางแยกทั้งหมด =1

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

จำนวนทางแยกทั้งหมด =0

ตัวอย่าง

#include <iostream>
using namespace std;
struct Point{ // points
    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;
}
// checking whether line segments intersect
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;
}
// checking whether 2 points are same
bool check_similar(Point A, Point B){
   // If found similiar then we are returning false that means no quad. can be formed
    if (A.x == B.x && A.y == B.y)
       return false;
   // returning true for not found similiar
    return true;
}
// Checking collinearity of three points
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;
}
// main function
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)
   // Checking whether any 3 points are collinear
   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 points found collinear
   if (flag == false){
       cout << "Number of quadrilaterals possible from the given points: 0";
       return 0;
   }
   // Checking if 2 points are same.
   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 similiar point exist
   if (same == false){
       cout << "Number of quadrilaterals possible from the given points: 0";
   return 0;
   }
   // checking whether diagonal intersect or not
    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

คำอธิบายของโค้ดด้านบน

รหัสนี้สามารถเข้าใจได้ในขั้นตอนต่อไปนี้ -

• ตรวจสอบว่าจุดสามจุดเป็น collinear หรือไม่ ถ้าใช่ ให้นับจำนวนสี่เหลี่ยม :0

• ตรวจสอบว่าจุดสองจุดใดเหมือนกันหรือไม่ และถ้าใช่ แสดงว่าเป็นจำนวนสี่เหลี่ยม :0

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

  • ถ้าใช่ ก็คือจำนวนสี่เหลี่ยม :1

  • ถ้าไม่เช่นนั้นจำนวนของคณะสี่คน :3

บทสรุป

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