寻找凸包（Graham扫描法）
题意描述 对任意给定的平面上的点集，求最小凸多边形使得点集中的点要么在凸多边形的边上，要么在凸多边形的内部。
Graham算法描述 1、在所有的点中找到一点p0，使得p0的纵坐标值最小，在有多个最小纵坐标的情况下，找横坐标最小的那一个。 2、将所有的点< p0, p1,…pn> 按规则（相对于p0的幅角从小到大，也就是绕p0逆时针，如有幅角相等的点，只保留离p0最远的那个，其他的删除）排序。 3、如果所剩的顶点数m小于3，不能构成凸包，retrun false; 4、将前三个点如空栈S。 5、for i = 3 to m while point next-to-top(S), point top(S), point i 不能构成一个左转的三角形 pop(S) push(point i, S) return S
栈S中的点即为构成凸包的点。 example 输入：
8 A -1 2 B 1 1 C 3 4 D 2 2 E 2 5 F 3 2 G 2 6 H 3 3输出：
B 1 1 F 3 2 C 3 4 G 2 6 A -1 2 #include<iostream> #include<algorithm> #include<cmath> #include<vector> #define INF 0x3f3f3f3f #define MAXN 50 using namespace std; struct point { char name; double x, y; }; vector<point> res; //数组模拟栈 vector<point> points; //点集 point p0; //y最小的情况下， x最小的点 double dis(point p1, point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); } bool cmp(const point p1, const point p2){ //atan2(y, x)返回向量xy和x轴正方向的夹角（-180到180） if (atan2(p1.y - p0.y, p1.x - p0.x) == atan2(p2.y - p0.y, p2.x - p0.x)) return dis(p0, p1) < dis(p0, p2); return atan2(p1.y - p0.y, p1.x - p0.x) < atan2(p2.y - p0.y, p2.x - p0.x); } bool istureleft(const point p0, const point p1, const point p2) { //p2是否相对于p1左转 double angle1 = atan2(p1.y - p0.y, p1.x - p0.x); double angle2 = atan2(p2.y - p0.y, p2.x - p0.x); if (angle1 < 0) angle1 += 2 * 3.1416; if (angle2 < 0) angle2 += 2 * 3.1416; return angle1 - angle2 < 0; } int main() { char c; double x, y; size_t i, n, index; while (cin >> n) { res.clear(); //清空栈 p0 = { ' ', INF, INF }; //初始化p0 points.clear(); for (i = 0; i < n; ++i) { cin >> c >> x >> y; points.push_back(point{ c, x, y }); if (y < p0.y || y == p0.y && x < p0.x) { index = i, p0 = { c, x, y }; } //更新p0 } sort(points.begin(), points.end(), cmp); index = 0; res.push_back(points[index++]); //前三个点进栈 res.push_back(points[index++]); res.push_back(points[index++]); for (; index < n; index++) {//对后边的每一个点 while (!istureleft(*(res.end() - 2), *(res.end() - 1), points[index])) res.erase(res.end() - 1); res.push_back(points[index]); } for (i = 0; i < res.size(); ++i) cout << res[i].name << " " << res[i].x << " " << res[i].y << endl; } return 0; }