分类目录归档:计算几何

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

判断线段相交

刚刚开始接触计算几何.. 之前按自己的思路写了一个线段相交却怎么也过不了某题..

最后发现果然还是自己智商拙计= =..

线段a, b相交的充要条件是:  a 叉积 b 的两个端点之积为负, b 叉积 a 的两个端点之积为负数, 而且两线段不平行.

下面给出部分代码.

bool Parallel(Point a, Point b, Point c, Point d) {return !dcmp(a.cross(b, a + d - c));}

bool SegCross(Point& a, Point& b, Point& c, Point& d)
{
    //一定要判断是否平行!
    if( !Parallel(a, b, c, d) && a.cross(b, c) * a.cross(b, d) <= 0 && c.cross(d, a) * c.cross(d, b) <= 0)
        return true;
    return false;
}

POJ 3304 Segments 计算几何基础,点的表示和叉积

题意:给出n条线段,求是否有一条直线能够与全部线段相交.

由于一条穿过所有的线段的直线,总可以通过平移来使得其通过某两个端点,故枚举端点,判断过端点的直线是否能穿过所有线段即可.

此题WA几次..究其原因为: 叉积之前需要判断给出的向量是否为0,为0则不能进行叉积操作..

刚刚开始做计算几何…orz各路神犇..希望能够快快长进!

# include <iostream>
# include <cmath>
# define sqr(x) ((x)*(x))
# define rep(x, n) for (int x = 0; x < n; ++x )
using namespace std;

const double eps = 1e-8;
int dcmp(double x){ return (x > eps) - (x < -eps);}

class Point
{
    public:
    double x, y;
    Point(){x = y = 0.0;}
    Point(double a, double b){ x = a; y = b; }

    inline Point operator -(const Point& b)
    { return Point(x-b.x, y-b.y);}

    inline double cross(const Point& b, const Point& c)
    { return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y); }

    inline double dis(const Point& b)
    { return sqrt( sqr(b.x - x) + sqr(b.y - y) ); }

}line[103][2];

int t, n;
bool ok;

void check(Point& a, Point& b)
{
    if ( dcmp(a.dis(b)) == 0 ) return;
    rep(i, n)
        if ( dcmp(a.cross(b, line[i][0]) * a.cross(b, line[i][1])) > 0 )
            return;
    ok = true;
    return;
}
int main()
{
    double x, y;
    cin >>t;
    while( t-- )
    {
        cin >>n;
        rep(i, n)
        {
            cin >> x >> y;
            line[i][0] = Point(x, y);
            cin >> x >> y;
            line[i][1] = Point(x, y);
        }
        ok = false;
        rep(i, n)
            for (int j = i+1; j < n; ++j )
            {
                if ( ok ) break;
                check(line[i][0], line[j][0]);
                check(line[i][0], line[j][1]);
                check(line[i][1], line[j][0]);
                check(line[i][1], line[j][1]);
            }
        if ( n == 1 ) ok = true;
        if ( ok ) cout << "Yes!" <<endl;
        else cout << "No!" << endl;
    }
    return 0;
}

Problem:Central Avenue Road 感觉第一次写的比较清晰的判断点线关系。

题意:给出一些整数点,然后求某两点的连线,使得左右两边的点数量相差小于1并且要求这条线最短。

根据y = kx + b 推 ax + by + c = 0,这两个直线方程,进而带入点判断正负来判断在直线的上/下(左/右)。

# include <cstdio>
# include <algorithm>
# include <cmath>
# define rep(x) for ( x = 1; x <= n; ++x )
using namespace std;
int x[107], y[107];
int n;

double ans;
inline double sqr(double x)
{ return x * x; }
inline double dis(int a, int b)
{
    double sum = sqr((double)(x[a] - x[b])) + sqr((double)(y[a] - y[b]));
    return sqrt(sum);
}
void test(int a, int b)
{
    int i, j;
    int l = 0, r = 0;
    double K, B;
    if ( x[a] == x[b] && y[a] == y[b] ) return;
    if ( x[a] == x[b] )
    {
        rep(i)
            if ( x[i] < x[a] ) l++;
            else if ( x[i] > x[a] ) r++;
    }
    else if ( y[a] == y[b] )
    {
        rep(i)
            if ( y[i] < y[a] ) l++;
            else if ( y[i] > y[a] ) r++;
    }
    else
    {
        K = (y[a] - y[b]) / ( x[a] - x[b] );
        B = y[a] - K * x[a];
        rep(i)
            if ( i == a || i == b ) continue;
            else
            {
                double tmp = K * x[i] - y[i] + B;
                if ( tmp > 0 ) l++;
                else if ( tmp < 0) r++;
            }
    }
    if ( abs(l-r) < 2 )
    {
        double d = dis(a, b);
        if ( d < ans ) ans = d;
    }
}
int main()
{
    int i, j;
    while ( scanf("%d", &n), n )
    {
        ans = 9999999.99;
        rep(i) scanf("%d%d", &x[i], &y[i]);
        rep(i)
            for ( j = i + 1; j <= n; ++j )
                test(i, j);
        if ( n == 1 ) ans = 0.0;
        printf("%.3f\n", ans);
    }
    return 0;
}