Đa Giác Lồi Trong C++

Giả sử chúng ta có danh sách các điểm tạo thành một đa giác khi nối theo thứ tự, chúng ta phải xác định đa giác này có lồi hay không (định nghĩa đa giác lồi). Có ít nhất 3 và tối đa 10.000 điểm. Tọa độ trong khoảng -10.000 đến 10.000.

Chúng ta giả định đa giác tạo bởi các điểm cho trước luôn là đa giác đơn giản, nghĩa là đúng hai cạnh cắt nhau tại mỗi đỉnh và các cạnh khác không cắt nhau. Ví dụ, đầu vào [[0,0],[0,1],[1,1],[1,0]] là lồi, trả về true.

Để giải quyết, chúng ta làm theo các bước:

Định nghĩa phương thức calc(ax, ay, bx, by, cx, cy) tính tích chéo: BAx = ax-bx, BAy = ay-by, BCx = cx-bx, BCy = cy-by; trả về BAx*BCy - BAy*BCx.
Từ phương thức chính: neg = false, pos = false, n = số điểm.
Với i từ 0 đến n-1: a = i, b = (i+1)%n, c = (i+2)%n.
crossProduct = calc(p[a][0], p[a][1], p[b][0], p[b][1], p[c][0], p[c][1]).
Nếu crossProduct < 0, neg = true; ngược lại nếu > 0, pos = true.
Nếu neg && pos, trả về false.
Trả về true.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#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));
}

Đầu vào

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

Đa Giác Lồi Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra