รูปหลายเหลี่ยมนูนในภาษา C++

สมมติว่าเรามีรายการจุดที่เป็นรูปหลายเหลี่ยมเมื่อเชื่อมติดกันตามลำดับ เราต้องค้นหาว่ารูปหลายเหลี่ยมนี้นูนหรือไม่ (นิยามรูปหลายเหลี่ยมนูน) เราต้องจำไว้ว่ามีอย่างน้อย 3 และสูงสุด 10,000 คะแนน และพิกัดอยู่ในช่วง -10,000 ถึง 10,000

เราสามารถสมมติได้ว่ารูปหลายเหลี่ยมที่เกิดจากจุดที่กำหนดให้เป็นรูปหลายเหลี่ยมธรรมดาเสมอ กล่าวคือ เราตรวจสอบให้แน่ใจว่าขอบทั้งสองตัดกันที่จุดยอดแต่ละจุด และขอบนั้นจะไม่ตัดกัน ดังนั้นหากอินพุตมีลักษณะดังนี้:[[0,0],[0,1],[1,1],[1,0]] จะเป็นนูน ดังนั้นค่าที่ส่งคืนจะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการ calc() ซึ่งจะใช้ ax, ay, bx, by, cx, cy ซึ่งจะทำงานดังนี้ -

• BAx :=axe – bx, BAy :=ay – โดย, BCx :=cx – bx, BCy :=cy - โดย

• จากวิธีหลักให้ทำดังนี้

• neg :=false และ pos :=false, n :=ขนาดของ point array

• สำหรับฉันอยู่ในช่วง 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 เป็นจริง ให้คืนค่าเท็จ

• คืนความจริง

ตัวอย่าง (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