#include <iostream> #include <vector> #include <math.h> #include <algorithm> using namespace std; using std::vector; class Solution { public: int chengbao(vector<vector<int>> &allPos) { vector<vector<int>> CH = allPos; CalcConvexHull(CH);//求凸包 show(CH,"凸包点:");//凸包点形成环，去掉环上的点会形成缺口 vector<vector<int>> innerPos = differenceSet(allPos, CH);//凸包里面的点 if(innerPos.empty()) return 0; //show(innerPos,"差集:"); int result = 0, gapSize = 1; while(CH.size() - gapSize >= 3){//凸包剩下4个点的时候肯定能找到解 result = testResultByFixGap(allPos, innerPos, CH, gapSize); if(result > 0) return result; gapSize++; } } private: void CalcConvexHull(vector<vector<int>> &vecSrc) { if(vecSrc.size() < 3) return; vector<int> ptBase = vecSrc.front(); //将第1个点预设为最小点 for(auto i = vecSrc.begin() + 1; i != vecSrc.end(); ++i){ //如果当前点的y值小于最小点，或y值相等，x值较小 if((*i)[1] < ptBase[1] || ((*i)[1] == ptBase[1] && (*i)[0] > ptBase[0])){ ptBase[0] = (*i)[0];//将当前点作为最小点 ptBase[1] = (*i)[1]; } } //cout<< "基点:"<<ptBase[0] << ptBase[1] <<endl; //计算出各点与基点构成的向量 for(auto i = vecSrc.begin(); i != vecSrc.end();){ //排除与基点相同的点，避免后面的排序计算中出现除0错误 if((*i)[0] == ptBase[0] && (*i)[1] == ptBase[1]){ i = vecSrc.erase(i); } else { (*i)[0] -= ptBase[0]; (*i)[1] -= ptBase[1]; ++i; } } sort(vecSrc.begin(), vecSrc.end(), &CompareVector);//按各向量与横坐标之间的夹角排序 vecSrc.erase(unique(vecSrc.begin(), vecSrc.end()), vecSrc.end());//删除相同的向量 //计算得到首尾依次相联的向量 vector<int> lastVec = vecSrc.back(); for(auto i = vecSrc.rbegin(); i != vecSrc.rend() - 1; ++i ){ auto iNext = i + 1; //向量三角形计算公式 (*i)[0] -= (*iNext)[0]; (*i)[1] -= (*iNext)[1]; } lastVec[0] *= -1, lastVec[1] *= -1; vecSrc.push_back(lastVec); //依次删除不在凸包上的向量 for (auto i = vecSrc.begin() + 1; i != vecSrc.end(); ++i){ //回溯删除旋转方向相反的向量，使用外积判断旋转方向 for (auto iLast = i - 1; iLast != vecSrc.begin();){ int v1 = (*i)[0] * (*iLast)[1], v2 = (*i)[1] * (*iLast)[0]; //如果叉积小于0，则无没有逆向旋转 如果叉积等于0，还需判断方向是否相逆 if(v1 > v2 || (v1 == v2 && (*i)[0] * (*iLast)[0] > 0 && (*i)[1] * (*iLast)[1] > 0)) break; //删除前一个向量后，需更新当前向量，与前面的向量首尾相连 向量三角形计算公式 (*i)[0] += (*iLast)[0], (*i)[1] += (*iLast)[1]; iLast = (i = vecSrc.erase(iLast)) - 1; } } //将所有首尾相连的向量依次累加，换算成坐标 vecSrc.front()[0] += ptBase[0], vecSrc.front()[1] += ptBase[1]; for(auto i = vecSrc.begin() + 1; i != vecSrc.end(); ++i){ (*i)[0] += (*(i - 1))[0], (*i)[1] += (*(i - 1))[1]; } } // 比较向量中哪个与x轴向量(1, 0)的夹角更大 static bool CompareVector(vector<int> &pt1, vector<int> &pt2) { float m1 = sqrt((float)(pt1[0] * pt1[0] + pt1[1] * pt1[1])); float m2 = sqrt((float)(pt1[0] * pt1[0] + pt1[1] * pt1[1])); float v1 = pt1[0] / m1, v2 = pt1[1] / m2; return (v1 > v2 || v1 == v2 && m1 < m2); } void show(vector<vector<int>> para, string explain){ cout<< explain <<endl; for(auto i:para){ for(auto j:i){ cout << j; } cout<<endl; } } //求差集A-B vector<vector<int>> differenceSet(vector<vector<int>> &setA, vector<vector<int>> &setB){ vector<vector<int>> result; for(auto i : setA){ if(find(setB.begin(), setB.end(), i) == setB.end()){ result.push_back(i); } } return result; } int testResultByFixGap(vector<vector<int>> &allPos, vector<vector<int>> &innerPos, vector<vector<int>> &CH, int gapSize){ for(int i = 0; i != CH.size(); i++){ vector<vector<int>> gapPos = getGapPos(CH, i, gapSize); show(gapPos,"缺口坐标:"); for(auto curPos : innerPos){//遍历内点的凸包会更高效 int x1 = curPos[0] - gapPos[0][0], y1 = curPos[1] - gapPos[0][1], x2 = gapPos[1][0] - curPos[0], y2 = gapPos[1][1] - curPos[1]; int v1 = x2 * y1, v2 = y2 * x1;//向量叉积判断方向 if(v1 > v2) return CH.size() - gapSize + innerPos.size(); } } return 0;//一个城堡也没有 } //求两个缺口坐标 输入：原始坐标，起始位置，删除元素个数 输出：删除后两端点 vector<vector<int>> getGapPos(vector<vector<int>> &Pos, int curIndex, int num){ vector<vector<int>> result; int lastIndex = Pos.size() - 1; int index1, index2;//缺口点坐标索引 index1 = curIndex - 1; if(index1 < 0) index1 = lastIndex; index2 = curIndex + num; if(index2 > lastIndex) index2 -= (lastIndex + 1); result.push_back(Pos[index1]); result.push_back(Pos[index2]); return result; } }; int main() { using std::vector; using std::string; using std::cout; Solution test; int numPos = 5; int allPos[numPos][2]={{0,0},{0,3},{3,0},{3,3},{1,1}}; vector<vector<int>> allPosVec; for(int i = 0; i < numPos; i++){ vector<int> Pos; Pos.push_back(allPos[i][0]); Pos.push_back(allPos[i][1]); allPosVec.push_back(Pos); } for(auto i:allPosVec){ for(auto j:i){ cout << j; } cout<<endl; } int res = test.chengbao(allPosVec); cout<< "最终结果"<< res <<endl; }