题意：一张图上给出n个点的坐标(xi,yi)，其中xi，yi均为正整数。记这n个点中，拥有最小y的点为A，你开始从点(0, yA)开始走向点A，然后，你可以随意选择径直走去另外的点，但必须满足一下3个条件：
1：只能向左转向。
2：走过的路径为留下一条红色的轨迹。
3：不能越过这条红色的轨迹。
问你最多能到达几个点，并且按到达的顺序输出各个点的标号。
思路：叉积的应用+dfs。易证：按照一定的顺序，每次选择当前左转角度最小的点（相等则选距离最近的点），必能按条件遍历所有的点。复习下叉积a * b的性质：
1. 向量a到向量b成逆时针时，上述结果大于0； 2. 向量a到向量b成顺时针时，上述结果小于0；
3. 向量a和向量b共线时（不论同向还是反向），上述结果等于0。
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int Max = 52; const double eps = 1e-8; struct Point{ int id, order; double x, y; }p[Max]; int n; bool cmp(Point &a, Point &b){ return a.order < b.order; } double xmult(Point sp, Point ep, Point op){ return (sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y); } double mydis(Point p1, Point p2){ double a = p1.x - p2.x; double b = p1.y - p2.y; return sqrt(a*a + b*b); } void dfs(int pre, int dep){ if(dep == n) return; int i, mi = 0; while(p[mi].order != -1) mi ++; // 选择一个没有经过的点作为当前的最优解点。 for(i = mi + 1; i < n; i ++){ // 用另外的没有经过的点与当前最优解点比较，求出最优解的点。 if(p[i].order != -1) continue; double w = xmult(p[mi], p[i], p[pre]); if(w < -eps) mi = i; else if(abs(w) < eps && mydis(p[pre], p[i]) < mydis(p[pre], p[mi])) mi = i; } p[mi].order = dep; dfs(mi, dep + 1); } int main(){ int t, i, mi; cin >> t; while(t --){ cin >> n; for(mi = i = 0; i < n; i ++){ cin >> p[i].id >> p[i].x >> p[i].y; p[i].order = -1; if(p[i].y < p[mi].y) mi = i; } p[mi].order = 0; dfs(mi, 1); sort(p, p + n, cmp); // 按经过的顺序排列。 cout << n; for(i = 0; i < n; i ++) cout << ' ' << p[i].id; cout << endl; } return 0; }极角排序：
分析：先找出最左下方的顶点(即纵坐标最小的顶点),然后对剩下的顶点按照对与左下点的极角排序,然后反复找最左下的点,反
复进行极角排序,同时记录排序后左下的顶点.
PS：如果给你一群凸包上的点，直接排序依次就好了 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-8; int sgn(double x) { if(fabs(x) < eps) return 0; if(x < 0) return -1; else return 1; } struct Point { double x, y; int index; Point(){} Point(double xx, double yy) : x(xx), y(yy){} Point operator - (const Point &a) const { return Point(x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x*a.y - y*a.x; } double operator *(const Point &a) const { return x*a.x + y*a.y; } }; double dist(Point a, Point b) { return sqrt((a-b)*(a-b)); } int pos; Point p[105]; bool cmp(Point a, Point b) { double temp = (a-p[pos])^(b-p[pos]); if(sgn(temp) == 0) return dist(p[pos], a) < dist(p[pos], b); else if(sgn(temp) < 0) return false; else return true; } int main() { int t; scanf("%d", &t); int n; while(t--) { scanf("%d", &n); double x, y; for(int i = 0; i < n; i++) { scanf("%d%lf%lf", &p[i].index, &p[i].x, &p[i].y); if(p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x)) swap(p[0], p[i]); } pos = 0; for(int i = 1; i < n; i++) { sort(p+i, p+n, cmp); pos++; } printf("%d ", n); for(int i = 0; i < n; i++) printf("%d%c",p[i].index, i == n-1 ? '\n' : ' '); } return 0; }