ধরুন আমাদের পয়েন্টের একটি তালিকা আছে যা ক্রমাগত যোগ করলে একটি পলিগন বানায়, আমাদের যাচাই করতে হবে এই পলিগনটি কনভেক্স কিনা (কনভেক্স পলিগন সংজ্ঞা)। কমপক্ষে ৩ এবং hoogst ১০,০০০ পয়েন্ট থাকবে। এবং কোঅরডিনেট -১০,০০০ থেকে ১০,০০০ পর্যন্ত।
আমরা অনুমান করতে পারি যে দেওয়া পয়েন্টগুলো থেকে গঠিত পলিগনটি সবসময় একটি সিম্পল পলিগন, অর্থাৎ প্রতিটি ভার্টেক্সে ঠিক দুটি এজ ছেদ করে এবং এজগুলো অন্যথায় একে অপরের সাথে ছেদ করে না। যেন ইনপুট [[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
