C++ এ উত্তল বহুভুজ

ধরুন আমাদের কাছে বিন্দুগুলির একটি তালিকা রয়েছে যা ক্রমিকভাবে যুক্ত হলে একটি বহুভুজ গঠন করে, আমাদের খুঁজে বের করতে হবে এই বহুভুজটি উত্তল কিনা (উত্তল বহুভুজ সংজ্ঞা)। আমাদের মনে রাখতে হবে যে কমপক্ষে 3 এবং সর্বাধিক 10,000 পয়েন্ট রয়েছে। এবং স্থানাঙ্কগুলি -10,000 থেকে 10,000 এর মধ্যে রয়েছে৷

আমরা অনুমান করতে পারি যে প্রদত্ত বিন্দু দ্বারা গঠিত বহুভুজটি সর্বদা একটি সাধারণ বহুভুজ, অন্য কথায়, আমরা নিশ্চিত করি যে ঠিক দুটি প্রান্ত প্রতিটি শীর্ষে ছেদ করে এবং সেই প্রান্তগুলি অন্যথায় একে অপরকে ছেদ করে না। সুতরাং যদি ইনপুটটি এরকম হয়:[[0,0],[0,1],[1,1],[1,0]], তাহলে এটি উত্তল, তাই প্রত্যাবর্তিত মান সত্য হবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি পদ্ধতি calc() সংজ্ঞায়িত করুন, এতে ax, ay, bx, by, cx, cy লাগবে, এটি নিম্নরূপ কাজ করবে -

• BAx :=ax – bx, BAy :=ay – by, BCx :=cx – bx, BCy :=cy - দ্বারা

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন

• neg :=মিথ্যা এবং pos :=মিথ্যা, n :=পয়েন্ট অ্যারের আকার

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • 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 সত্য হয়, তাহলে মিথ্যা ফেরত দিন

• প্রত্যাবর্তন সত্য

উদাহরণ (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