判断正负号
给定一个double类型的数，判断它的符号；
const double eps = 1e-8;
int cmp(double x) {
if (fabs(x) < eps) return 0;
if (x > 0) return 1;
return -1;
}
通过acos计算PI的值；计算sqr平方值；
const double pi = acos(-1.0);
inline double sqr(double x) {
return x * x;
}
计算几何点类
设计了一个二维点类，可以进行一些向量运算。
det：计算两个向量的叉积；
dot：计算两个向量的点积；
dist：计算两个点的距离；
rotate_point：
o
p
⃗
\vec{op}
o
p
绕原点逆时针旋转A（弧度）；
struct point
{
double x, y;
point() :x(0.0), y(0.0) {}
point(double a, double b) :x(a), y(b) {}
void input() { scanf("%lf%lf", &x, &y); }
friend point operator+(const point& a, const point& b) {
return point(a.x + b.x, a.y + b.y);
}
friend point operator-(const point& a, const point& b) {
return point(a.x - b.x, a.y - b.y);
}
friend point operator*(const point& a, const point& b) {
return point(a.x * b.x, a.y * b.y);
}
friend point operator*(const double& a, const point& b) {
return point(a * b.x, a * b.y);
}
friend point operator*(const point& a, const double& b) {
return point(b * a.x, b * a.y);
}
friend point operator/(const point& a, const double& b) {
return point(a.x / b, a.y / b);
}
double norm() {
return sqrt(sqr(x) + sqr(y));
}
};
double det(const point& a, const point& b) {
return a.x * b.y - a.y * b.x;
}
double dot(const point& a, const point& b) {
return a.x * b.x + a.y * b.y;
}
double dist(const point& a, const point& b) {
return (a - b).norm();
}
point rotate_point(const point& p, double A) {
double tx = p.x;
double ty = p.y;
return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A));
}
点积
（也叫内积）结果 为 x1 * x2 + y1 * y2 = |
a
⃗
\vec{a}
a
||
b
⃗
\vec{b}
b
| cos<
a
⃗
\vec{a}
a
,
b
⃗
\vec{b}
b
>，可以理解为向量a在向量b上投影的长度乘以向量b的长度。
叉积
（也叫外积）的模为 x1 * y2 – x2 * y1 = |
a
⃗
\vec{a}
a
||
b
⃗
\vec{b}
b
| sin<
a
⃗
\vec{a}
a
,
b
⃗
\vec{b}
b
>，可以理解为平行四边形的有向面积（三维以上为体积）。外积的方向垂直于这两个方向。
计算几何线段类
线段类使用一个有向线段表示，线段类的运算使用向量运算；内部使用线段的两个点记录，用a->b表示有向线段；
struct line
{
point a;// begin
point b;// end
line() {}
line(point x, point y) :a(x), b(y) {}
};
// 用两个点
line point_make_line(const point a, const point b) {
return line(a, b);
}
// 计算p点到线段st的距离
double dis_point_segment(const point p, const point s, const point t) {
if (cmp(dot(p - s, t - s)) == 0) return (p - s).norm();
if (cmp(dot(p - t, s - t)) == 0) return (p - t).norm();
return fabs(det(s - p, t - p) / dist(s, t));
}
// 计算p点在线段st上的投影点cp
void PointProjLine(const point p, const point s, const point t, point& cp) {
double r = dot((t - s), (p - s)) / dot(t - s, t - s);
cp = s + r * (t - s);
}
// 判断p点是否在线段st上（包括端点）
bool PointOnSegment(point p, point s, point t) {
return cmp(det(p - s, t - s)) == 0 && cmp(dot(p - s, p - t)) <= 0;
}
// 判断线段a和线段b是否平行；
bool parallel(line a, line b) {
return !cmp(det(a.a - a.b, b.a - b.b));
}
// 判断线段a和线段b是否相交，如果相交则返回true且交点保存在res中；
bool line_make_point(line a, line b, point& res) {
if (parallel(a, b)) return false;
double s1 = det(a.a - b.a, b.b - b.a);
double s2 = det(a.b - b.a, b.b - b.a);
res = (s1 * a.b - s2 * a.a) / (s1 - s2);
return true;
}
// 将线段a沿着法线方向平移距离len得到的线段
line move_d(line a, const double& len) {
point d = a.b - a.a;
d = d / d.norm();
d = rotate_point(d, pi / 2);
return line(a.a + d * len, a.b + d * len);
}
计算p点到线段st的距离
计算距离的特殊情况是p点与s点的连线垂直于st向量或者p点与t点的连线垂直于st向量时，直接使用ps或者pt向量的模；
一般情况下，使用面积法计算p点到st段上的投影，即使用ps向量和st向量的叉积表示两个向量形成的平行四边形的面积，除以st的线段长度，就是p点到st向量的距离；
具体代码，参照之前代码的dis_point_segment函数；