2013-team5/geometry

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cmath>

using namespace std;

const double EPS = 1e-8;

struct point
{
    double x, y;
    point(){}
    point(double xx, double yy) : x(xx), y(yy){}
}p[maxN];

struct seg
{
    point p1, p2;
    seg(){}
    seg(point pp1, point pp2) : p1(pp1), p2(pp2) {}
    seg(double x1, double y1, double x2, double y2) : p1(point(x1, y1)), p2(point(x2, y2)) {}
};

double dist(point p1, point p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}


double crossA(point p1, point p2)
{
    return (p1.x * p2.y - p2.x * p1.y);
}

double crossB(point p1, point p2, point P)
{
    return (p1.x - P.x) * (p2.y - P.y) - (p2.x - P.x) * (p1.y - P.y);
}

bool check_seg(seg L1, seg L2)     //线段相交
{
    return max(L1.p1.x, L1.p2.x) >= min(L2.p1.x, L2.p2.x) &&
           max(L1.p1.y, L1.p2.y) >= min(L2.p1.y, L2.p2.y) &&
           max(L2.p1.x, L2.p2.x) >= min(L1.p1.x, L1.p2.x) &&
           max(L2.p1.y, L2.p2.y) >= min(L1.p1.y, L1.p2.y) &&
           crossB(L1.p1, L2.p2, L2.p1) * crossB(L2.p2, L1.p2, L2.p1) >= 0 &&
           crossB(L2.p1, L1.p2, L1.p1) * crossB(L1.p2, L2.p2, L1.p1) >= 0;
}

bool PIS(point P, seg L)           //判断点是否在直线上
{
    if (P.x > max(L.p1.x, L.p2.x)) return 0;
    if (P.x < min(L.p1.x, L.p2.x)) return 0;
    if (P.y > max(L.p1.y, L.p2.y)) return 0;
    if (P.y < min(L.p1.y, L.p2.y)) return 0;
    return fabs(crossB(L.p1, L.p2, P)) < EPS;
}
}}}

#include <cmath>
using namespace std;
const double EPS = 1e-8;
struct point
{
    double x, y;
    point(){}
    point(double xx, double yy) : x(xx), y(yy){}
}p[maxN];
struct seg
{
    point p1, p2;
    seg(){}
    seg(point pp1, point pp2) : p1(pp1), p2(pp2) {}
    seg(double x1, double y1, double x2, double y2) : p1(point(x1, y1)), p2(point(x2, y2)) {}
};
double dist(point p1, point p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double crossA(point p1, point p2)
{
    return (p1.x * p2.y - p2.x * p1.y);
}
double crossB(point p1, point p2, point P)
{
    return (p1.x - P.x) * (p2.y - P.y) - (p2.x - P.x) * (p1.y - P.y);
}
bool check_seg(seg L1, seg L2)     //线段相交
{
    return max(L1.p1.x, L1.p2.x) >= min(L2.p1.x, L2.p2.x) &&
           max(L1.p1.y, L1.p2.y) >= min(L2.p1.y, L2.p2.y) &&
           max(L2.p1.x, L2.p2.x) >= min(L1.p1.x, L1.p2.x) &&
           max(L2.p1.y, L2.p2.y) >= min(L1.p1.y, L1.p2.y) &&
           crossB(L1.p1, L2.p2, L2.p1) * crossB(L2.p2, L1.p2, L2.p1) >= 0 &&
           crossB(L2.p1, L1.p2, L1.p1) * crossB(L1.p2, L2.p2, L1.p1) >= 0;
}
bool PIS(point P, seg L)           //判断点是否在直线上
{
    if (P.x > max(L.p1.x, L.p2.x)) return 0;
    if (P.x < min(L.p1.x, L.p2.x)) return 0;
    if (P.y > max(L.p1.y, L.p2.y)) return 0;
    if (P.y < min(L.p1.y, L.p2.y)) return 0;
    return fabs(crossB(L.p1, L.p2, P)) < EPS;
}