题目大意为,给定一些点,以最下且最左的那个点位起点,只能左拐,且路径不能交叉,求使得路径经过点数最多的走法.输出这条路径的长度和按顺序经过的点.
显然,只要沿着最外围走,所有点都可以被走到,使用求凸包的卷包裹法稍加更改,即可走出这样一条路径.
# include <iostream> # include <algorithm> # include <cmath> # define rep(x, n) for (int x = 0; x < (n); ++x ) using namespace std; int t, n; class Point { public: double x, y; int id; Point(){x = 0; y = 0;} Point(const double& x, const double& y, const int id = 0) { this->x = x; this->y = y; this->id = id; } inline bool operator <(const Point& a)const { return (y - a.y)? y < a.y : x < a.x; } inline Point operator +(const Point& a) { return Point(x + a.x, y + a.y); } inline Point operator -(const Point& a) { return Point(x - a.x, y - a.y); } inline double dot(const Point& a) { return x * a.x + y * a.y; } inline double Dis(const Point& a) { return sqrt( (*this - a).dot(*this - a)); } inline double cross(const Point& b, const Point& c) { return (b.x - x) * (c.y - y) - (b.y - y) * (c.x - x); } }p[53]; bool v[53]; int res[53]; int main() { int q; double x, y; cin >> t; while ( t-- ) { cin >> n; rep(i, n) { cin >> q >> x >> y; p[i] = Point(x, y, q); v[i] = false; } sort(p, p+n); v[0] = true; res[0] = 0; rep(i, n-1) { rep(j, n) if ( !v[j] ) res[i+1] = j; rep(j, n) { if ( v[j] ) continue; double tmp = p[res[i]].cross(p[res[i+1]], p[j]); if ( tmp < 0 ) res[i+1] = j; } v[res[i+1]] = true; } cout << n; rep(i, n) cout << ' '<< p[res[i]].id; cout << endl; } return 0; }