计算几何

#include <cmath> #include <iostream> #define ll long long using namespace std; const double pi = acos(-1.0); // 高精度圆周率 const double eps = 1e-8; //偏差值 int sgn(double x) { //判断x是否等于0 if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } int dcmp(double x, double y) { //比较两个浮点数：0为相等；-1为小于；1为大于 if (fabs(x - y) < eps) return 0; else return x < y ? -1 : 1; } //点 struct Point { double x, y; Point() {} Point(double x, double y) : x(x), y(y) {} //向量运算 Point operator+(Point B) { return Point(x + B.x, y + B.y); } Point operator-(Point B) { return Point(x - B.x, y - B.y); } Point operator*(double k) { return Point(x * k, y * k); } Point operator/(double k) { return Point(x / k, y / k); } bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; } }; //两点之间距离 double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); } //向量 typedef Point Vector; //点积 //若dot(A,B)>0,A与B的夹角为锐角； //若dot(A,B)<0,A与B的夹角为钝角； //若dot(A,B)=0,A与B的夹角为直角； double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } //求向量A的长度 double Len(Vector A) { return sqrt(Dot(A, A)); } //求长度的平方，避免开方运算 double Len2(Vector A) { return Dot(A, A); } //求向量A与B的夹角大小 double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Len(A) / Len(B)); } //叉积 //叉积有正负 // AXB>0,B在A的逆时针方向 // AXB<0,B在A的顺时针方向 // AXB=0,B与A共线，方向不确定 double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } //计算两向量构成的平行四边形的有向四边形的有向面积（面积有正负） //以A为公共点，得到两个向量B-A和C-A,它们构成的平行四边形面积 double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); } //计算三点构成的三角形的面积 // 3个点A，B，C构成的三角形的面积等于平行四边形面积Area2(A,B,C)的1/2 double Area(Point A, Point B, Point C) { return Cross(B - A, C - A) * 0.5; } //向量旋转 //向量A逆时针旋转的角度为rad Vector Rotate(Vector A, double rad) { return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); } //有时需要求单位法向量，即逆时针转90，然后求单位值 Vector Normal(Vector A) { return Vector(-A.y / Len(A), A.x / Len(A)); } //用叉积检查两个向量是否平行或重合 bool Parallel(Vector A, Vector B) { return sgn(Cross(A, B)) == 0; } //直线 struct Line { Point p1, p2; Line() {} //两点式确定直线 Line(Point p1, Point p2) : p1(p1), p2(p2) {} //点斜式确定直线，0<=angle<pi Line(Point p, double angle) { p1 = p; if (sgn(angle - pi / 2) == 0) { p2 = (p1 + Point(0, 1)); } else { p2 = (p1 + Point(1, tan(angle))); } } //标准式确定直线，ax+by+c=0 Line(double a, double b, double c) { if (sgn(a) == 0) { p1 = Point(0, -c / b); p2 = Point(1, -c / b); } else if (sgn(b) == 0) { p1 = Point(-c / a, 0); p2 = Point(-c / a, 1); } else { p1 = Point(0, -c / b); p2 = Point(1, (-c - a) / b); } } }; //线段 //两点式定义线段 typedef Line Segment; //点和直线的位置关系 int Point_line_relation(Point p, Line v) { int c = sgn(Cross(p - v.p1, v.p2 - v.p1)); if (c < 0) return 1; // 1:p在v的左边 if (c > 0) return 2; // 2:p在v的右边 return 0; // 1:p在v上 } //点和线段的位置关系 bool Point_on_seg(Point p, Line v) { return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(Dot(p - v.p1, p - v.p2)) <= 0; } //点到直线的距离 double Dis_point_line(Point p, Line v) { return fabs(Cross(p - v.p1, v.p2 - v.p1)) / Distance(v.p1, v.p2); } //点在支线上的投影 Point Point_line_proj(Point p, Line v) { double k = Dot(v.p2 - v.p1, p - v.p1) / Len2(v.p2 - v.p1); return v.p1 + (v.p2 - v.p1) * k; } //点关于直线的对称点 Point Point_line_symmetry(Point p, Line v) { Point q = Point_line_proj(p, v); return Point(2 * q.x - p.x, 2 * q.y - p.y); } //点到直线的距离 double Dis_point_seg(Point p, Segment v) { if (sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0) return Dis_point_line(p, v); //点的投影在线段上 } //两条直线的位置关系 int Line_relation(Line v1, Line v2) { if (sgn(Cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) { if (Point_line_relation(v1.p1, v2) == 0) return 1; // 1:重合 else return 0; // 0:平行 } return 2; // 2:相交 } //两条直线的交点 //先保证AB,CD不共线，不平行！！！ Point Cross_Point(Point a, Point b, Point c, Point d) { // Line1: ab,Line2: cd double s1 = Cross(b - a, c - a); double s2 = Cross(b - a, d - a); //叉积有正负 return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1); } //判断两个线段是否相交 bool Cross_segment(Point a, Point b, Point c, Point d) { // Line1: ab,Line2: cd double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a); double d1 = Cross(d - c, a - c), d2 = Cross(d - c, b - c); return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0; // 1：相交 0：不相交 } //求两个线段的交点 //先判断两条线段是否相交，若相交，问题转化为两条直线求交点