C++ का प्रयोग करते हुए दिए गए बिंदुओं से संभव चतुर्भुजों की संख्या ज्ञात कीजिए

एक चतुर्भुज यूक्लिडियन समतल ज्यामिति में चार शीर्षों और चार किनारों वाला एक बहुभुज बनाता है। नाम 4-गॉन आदि। चतुर्भुज के अन्य नामों में शामिल हैं और कभी-कभी उन्हें एक वर्ग, प्रदर्शन शैली आदि के रूप में भी जाना जाता है।

इस लेख में, हम दिए गए बिंदुओं से संभव चतुर्भुजों की संख्या का पता लगाने के तरीकों की व्याख्या करेंगे। इस समस्या में, हमें यह पता लगाने की आवश्यकता है कि कार्तीय तल में दिए गए चार बिंदुओं (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).

समाधान खोजने के लिए दृष्टिकोण

• हम पहले जाँच करेंगे कि क्या 4 में से 3 बिंदु संरेख हैं और यदि हाँ, तो बिन्दुओं से कोई चतुर्भुज नहीं बनाया जा सकता है ।

• उसके बाद, हम जाँच करेंगे कि क्या 4 में से कोई 2 बिंदु समान हैं और यदि हाँ, तो कोई चतुर्भुज नहीं बनाया जा सकता है ।

• अब, हम जांच करेंगे कि विकर्ण प्रतिच्छेद करता है या नहीं। यदि हाँ, तो केवल एक संभावित चतुर्भुज बनाया जा सकता है, एक उत्तल चतुर्भुज . कहा जाता है ।

चौराहे की कुल संख्या =1

यदि विकर्ण प्रतिच्छेद नहीं करते हैं, तो तीन संभावित चतुर्भुज बन सकते हैं, जिन्हें अवतल चतुर्भुज कहा जाता है।

चौराहे की कुल संख्या =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

उपरोक्त कोड की व्याख्या

इस कोड को निम्नलिखित चरणों में समझा जा सकता है -

• जाँच करना कि क्या कोई तीन बिंदु संरेख हैं और यदि हाँ, तो एक क्वाड की संख्या। :0

• जाँच करना कि क्या कोई दो बिंदु समान हैं और यदि हाँ, तो एक क्वाड की संख्या। :0

• जाँच करना कि क्या कोई रेखा खंड प्रतिच्छेद करता है:

  • यदि हाँ, तो एक क्वाड की संख्या। :1

  • यदि नहीं, तो क्वाड्स की संख्या। :3

निष्कर्ष

इस लेख में, हमने दिए गए 4 बिंदुओं से बनने वाले सभी संभावित चतुर्भुजों को खोजने का हल किया है। हम समझते हैं कि कैसे चतुर्भुजों की संख्या संरेखता, प्रतिच्छेदन और अभिविन्यास पर निर्भर करती है। हम इसके लिए C++ प्रोग्राम भी लिखते हैं, और हम इस प्रोग्राम को C, Java, और python जैसी किसी भी अन्य भाषा में लिख सकते हैं।