C++ में कन्वेक्स पॉलीगॉन

मान लीजिए हमारे पास पॉइंट्स की एक लिस्ट है जो क्रमिक रूप से जुड़ने पर एक पॉलीगॉन बनाती है, हमें यह पता लगाना है कि क्या यह पॉलीगॉन कन्वेक्स (उत्तल) है। ध्यान रखें कि कम से कम 3 और अधिकतम 10,000 पॉइंट्स हैं। और कोऑर्डिनेट्स -10,000 से 10,000 की रेंज में हैं।

हम मान सकते हैं कि दिए गए पॉइंट्स से बना पॉलीगॉन हमेशा एक सिंपल पॉलीगॉन है, दूसरे शब्दों में, हम सुनिश्चित करते हैं कि प्रत्येक वर्टेक्स पर ठीक दो एजेस इंटरसेक्ट करती हैं और एजेस अन्यथा एक-दूसरे को इंटरसेक्ट नहीं करती हैं। उदाहरण के लिए, अगर इनपुट है: [[0,0],[0,1],[1,1],[1,0]], तो यह कन्वेक्स है, इसलिए रिटर्न वैल्यू true होगी।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• calc() नाम का एक मेथड डिफाइन करें, जो ax, ay, bx, by, cx, cy लेगा, यह निम्न की तरह काम करेगा:

  • BAx := ax - bx, BAy := ay - by, BCx := cx - bx, BCy := cy - by

• मेन मेथड से निम्न करें:

  • neg := false और pos := false, n := पॉइंट्स ऐरे का साइज

  • i को 0 से n-1 तक लूप करें:

    • a := i, b := (i + 1) mod n और c := (i + 2) mod n

    • cross_prod := calc(p[a][0], p[a][1], p[b][0], p[b][1], p[c][0], p[c][1])

    • अगर cross_prod < 0, तो neg := true, अन्यथा जब cross_prod > 0, तो pos := true

    • अगर neg और pos दोनों true हैं, तो false लौटाएं

  • true लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        bool neg = false;
        bool pos = false;
        int n = points.size();
        for(int i = 0; i < n; i++){
            int a = i;
            int b = (i + 1) % n;
            int c = (i + 2) % n;
            int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
            if(crossProduct < 0) neg = true;
            else if(crossProduct > 0) pos = true;
            if(neg && pos) return false;
        }
        return true;
    }
    int calc(int ax, int ay, int bx, int by, int cx, int cy){
        int BAx = ax - bx;
        int BAy = ay - by;
        int BCx = cx - bx;
        int BCy = cy - by;
        return (BAx * BCy - BAy * BCx);
    }
};

int main(){
    vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
    Solution ob;
    cout << (ob.isConvex(v));
}

इनपुट

[[0,0],[0,1],[1,1],[1,0]]

आउटपुट

1