阿里笔试题-城堡问题 求解

我也是这道题，也没做出来，我当时的思路是先求凸包上的点，然后穷举剩下所有点中每两点连成的直线，找线两侧存在的最大点数。。。不过这样复杂度好高，代码量也好多，没信心能写完，也确实没写完。后来和同学讨论，同学给的方法是基于jarvis步进法做改进，找夹角第二小的点，复杂度能到O（kn）。

求助，有想法的同学可以把思路跟我说下吗

这是今年的题目嘛

对不起，我不是要灌水，希望大家帮帮忙

什么是凸焦点？

我也是这道题……测试的时候没编出来

居然和我的一模一样

什么岗位的

把他看成二维坐标，分四种情况判断。都大于x,都小于x,都大于y,都小于y

求问，在线编程必须做吗？感觉不会呀

昨天这道题，算法，图像方面，没有做出来

两点成直线统计两边个数，排除凸点

参考《算法导论》里面的凸包问题

import java.util.ArrayList; import java.util.Scanner; public class Castle { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int num = sc.nextInt();//城堡个数 ArrayList<Point> aList = new ArrayList<Point>(); //将城堡存入ArrayList中 for(int i=0;i<num;i++){ double x = Double.parseDouble(sc.next()); double y = Double.parseDouble(sc.next()); Point point = new Point(x,y); aList.add(point); } // for(Point point:aList) // System.out.println(point); System.out.println(getMax(aList)); // for(Point point:aList) // System.out.println(point); sc.close();//关闭流 } public static int getMax(ArrayList<Point> Points) { int result = 0; int size = Points.size(); if(size<4)//小于四座城堡，则都是凸焦点 return 0; for(int i=0;i<size;i++){ for(int j=0;j<size;j++){//以i,j两城堡为射线，遍历剩下的城堡 if(i==j) continue;//重复的跳过 int n1 = 0;//射线一侧的城堡 int n2 = 0;//射线另一侧的城堡 int n = 2;//至少有i,j两个城堡 double theta1 = 0;//射线一侧最大夹角 double theta2 = 0;//射线另一侧最大夹角 for(int k=0;k<size;k++){ if(k==i||k==j) continue;//重复的跳过 Point tmp = help(Points.get(i), Points.get(j), Points.get(k)); if(tmp.y==0) //位于射线上 n++; else{ if(tmp.x>0){//射线一侧 n1++; theta1 = Math.max(theta1, tmp.y); }else if(tmp.x<0){//射线另一侧 n2++; theta2 = Math.max(theta2, tmp.y); } } } if(Math.acos(-1)<theta1+theta2){//判断是否凸焦点 n1 = n + Math.max(n1, n2); result = Math.max(n1, result); } } } return result; } public static Point help(Point point1,Point point2,Point point3) {//计算三个点的夹角和第三个点在射线的两侧 Point result = new Point(); Point p1 = new Point(point1.x,point1.y); Point p2 = new Point(point2.x,point2.y); Point p3 = new Point(point3.x,point3.y); //向量1 p2.x -= p1.x; p2.y -= p1.y; //向量2 p3.x -= p1.x; p3.y -= p1.y; result.x = p2.x*p3.y - p3.x*p2.y; //正负值判断在射线的两端 result.y = Math.acos((p2.x * p3.x + p2.y * p3.y) / Math.sqrt((p2.x * p2.x + p2.y * p2.y) * (p3.x * p3.x + p3.y * p3.y))); //向量法计算夹角（0——π）弧度制 return result; } } class Point{ double x = 0; double y = 0; public Point(){} public Point(double x,double y) { this.x = x; this.y = y; } @Override public String toString() { return "("+this.x+" , "+this.y+")"; } } 觉得对的小伙伴，记得点赞哦~~

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

#include <iostream> #include <vector> #include <numeric> #include <limits> using namespace std; /** 请完成下面这个函数，实现题目要求的功能 **/  /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^  **/ int castle(vector < double > points,int size) { int ans=0; int left=0,right=0; double k=0,b=0; int max=0; int tudian=0; for(int i=0;i<size-1;i++){   for(int j=i+1;j<size;j++){      k=(points[j]-points[i])/(j-i);      b=points[j]-k*j;      left=0;right=0;      for(int p=i+1;p<size;p++){         if(p!=j){            if(k*p+b<points[p]) left++;             else right++;         }     }    if(left==0||right==0) { tudian++;continue;}     else{max=left>right?left:right;          ans=max>ans?max:ans;}         } } if(tudian==size) ans=0; return ans; } int main() {     int res;     int _points_size = 0;     cin >> _points_size;     cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');     vector<double> _points;     double _points_item;     for(int _points_i=0; _points_i<_points_size; _points_i++) {         cin >> _points_item;         cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');         _points.push_back(_points_item);     }              res = castle(_points,_points_size);     cout << res << endl;          return 0; }

我这题当时想的是第一次找凸包，找到凸包后剩下的那些点再找凸包，因为第二次找到的凸包上面的点就是将军所占的候选点。至于在候选点如何判断哪一个是最好的点，还没有想出具体的方法，但是通过最外面凸包上面连续的k= 3  4  5  6....的点，依次构造 三角形 四边形 五边形 六边形等等就会找到最优的点。比如构建的很多三角形里面存在一个三角形包含一个候选点，那么肯定只有一个点看不到，四边形的话就是两个点看不到，L边型的话就是L-2个点看不到。但是这样好复杂啊。。。

感觉只能想到先找一次凸包然后对剩下的点n^2枚举直线判断直线两侧点的数量。。

//1.将军不能站在凸集点上。构建凸点集：对任意一个点，若能找到3个点，使得该点在这三个点构成的三角形内，则认为该点不属于凸点集，否则属于凸点集。 //2.对于不在凸点集中的点，遍历360°空间，构建所有的直线（用点构建），计算所有点到这条直线的距离，统计正负号。 //3.选择某条直线上正负号数目最大的作为函数输出。 //好复杂-.-!   写了4个注释就交了，唉