POJ 1696 Space Ant 稍微修改的卷包裹法.

题目大意为,给定一些点,以最下且最左的那个点位起点,只能左拐,且路径不能交叉,求使得路径经过点数最多的走法.输出这条路径的长度和按顺序经过的点.

显然,只要沿着最外围走,所有点都可以被走到,使用求凸包的卷包裹法稍加更改,即可走出这样一条路径.

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

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>