資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的凸多邊形
假設我們有一系列點，這些點按順序連線起來形成一個多邊形，我們需要判斷這個多邊形是否是凸多邊形（凸多邊形的定義）。需要注意的是，點的數量至少為3，最多為10,000個。座標範圍在-10,000到10,000之間。
我們可以假設由給定點形成的多邊形始終是一個簡單多邊形，換句話說，我們確保在每個頂點處恰好有兩個邊相交，並且邊在其他地方不相交。因此，如果輸入類似於：[[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);
}
};
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
更新於：2020年4月29日
2K+ 次瀏覽
廣告