C++ . में उत्तल बहुभुज

मान लीजिए कि हमारे पास उन बिंदुओं की एक सूची है जो क्रमिक रूप से जुड़ने पर बहुभुज बनाते हैं, हमें यह पता लगाना होगा कि क्या यह बहुभुज उत्तल है (उत्तल बहुभुज परिभाषा)। हमें यह ध्यान रखना होगा कि कम से कम 3 और अधिक से अधिक 10,000 अंक हों। और निर्देशांक -10,000 से 10,000 की सीमा में हैं।

हम मान सकते हैं कि दिए गए बिंदुओं से बना बहुभुज हमेशा एक साधारण बहुभुज होता है, दूसरे शब्दों में, हम यह सुनिश्चित करते हैं कि बिल्कुल दो किनारे प्रत्येक शीर्ष पर प्रतिच्छेद करते हैं और किनारे अन्यथा एक दूसरे को नहीं काटते हैं। तो अगर इनपुट इस तरह है:[[0,0], [0,1], [1,1], [1,0]], तो यह उत्तल है, इसलिए लौटाया गया मान सत्य होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक विधि कैल्क () को परिभाषित करें, यह कुल्हाड़ी, ay, bx, by, cx, cy लेगा, यह निम्नानुसार काम करेगा -

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

• मुख्य विधि से निम्न कार्य करें

• नकारात्मक:=झूठा और स्थिति:=झूठा, एन:=अंक सरणी का आकार

• मेरे लिए 0 से n - 1 की सीमा में

  • ए:=आई, बी:=(i + 1) मॉड एन और सी:=(i + 2) मॉड एन

  • cross_prod :=कैल्क(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

  • अगर नकारात्मक और स्थिति सही है, तो झूठी वापसी करें

• सही लौटें

उदाहरण (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);
   }
};
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