2018-2-23 改
- #include<cstdio>
- #include<cmath>
- using namespace std;
- namespace X
- {
- const double eps=1e-10;
- struct Point
- {
- double x,y;
- Point(double x=0,double y=0):x(x),y(y){}
- };
- typedef Point Vec;
- Vec operator+(const Vec& a,const Vec& b)
- {
- return Vec(a.x+b.x,a.y+b.y);
- }
- Vec operator-(const Vec& a,const Vec& b)
- {
- return Vec(a.x-b.x,a.y-b.y);
- }
- Vec operator*(const double& a,const Vec& b)
- {
- return Vec(a*b.x,a*b.y);
- }
- Vec operator*(const Vec& a,const double& b)
- {
- return Vec(b*a.x,b*a.y);
- }
- Vec operator/(const Vec& a,const double& b)
- {
- return Vec(a.x/b,a.y/b);
- }
- int dcmp(double x)
- // 正为 1, 负为 - 1,0 为 0
- {
- if(fabs(x)<eps) return 0;
- return x<0?-1:1;
- }
- bool operator==(const Vec& a,const Vec& b)
- // 判向量相等
- {
- return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
- }
- double dot(const Vec& a,const Vec& b)
- // 点积
- {
- return a.x*b.x+a.y*b.y;
- }
- double cross(const Vec& a,const Vec& b)
- // 叉积
- {
- return a.x*b.y-a.y*b.x;
- }
- double len(const Vec& x)
- // 向量长度
- {
- return sqrt(dot(x,x));
- }
- double angle(const Vec& a,const Vec& b)
- // 夹角, 0~180°
- {
- return acos(dot(a,b)/len(a)/len(b));
- }
- double angle1(const Vec& a,const Vec& b)
- // 夹角, 带方向, a 到 b 逆时针为正, 顺时针为负, 共线为 0
- {
- return acos(dot(a,b)/len(a)/len(b))*(dcmp(cross(a,b)));
- }
- Vec rotate(const Vec& a,const double& rad)
- // 旋转, 正为逆时针, 负为顺时针
- {
- return Vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
- }
- Vec normal(const Vec& x)
- // 单位法线, 左转 90° 后除以自身长度
- {
- double l=len(x);
- return Vec(-x.y/l,x.x/l);
- }
- Vec normal1(const Vec& x)
- // 法线, 不归一化
- {
- return Vec(-x.y,x.x);
- }
- Point lineline(const Point& p,const Vec& v,const Point& q,const Vec& w)
- // 直线交点, GetLineIntersection
- {
- return p+v*cross(w,p-q)/cross(v,w);
- }
- double ptline(const Point& p,const Point& a,const Point& b)
- //point_to_line, 点到直线距离, DistanceToLine
- {
- Vec v1=b-a,v2=p-a;
- return fabs(cross(v1,v2)/len(v1));
- }
- double ptseg(const Point& p,const Point& a,const Point& b)
- //point_to_segment, 点到线段距离, DistanceToSegment
- {
- if(a==b) return len(p-a);
- //Vec v1=b-a,v2=a-p,v3=p-b;
- Vec v1=b-a,v2=p-a,v3=p-b;
- if(dcmp(dot(v1,v2))<0) return len(v2);
- else if(dcmp(dot(v1,v3))>0) return len(v3);
- else return fabs(cross(v1,v2)/len(v1));
- }
- double area2(const Point& a,const Point& b,const Point& c)
- // 叉积对应平行四边形的面积
- {
- return cross(b-a,c-a);
- }
- double thrarea(const Point& a,const Point& b,const Point& c)
- // 三角形面积, 绝对值
- {
- return fabs(cross(b-a,c-a)/2);
- }
- bool ifpar(const Vec& a,const Vec& b)
- //ifParallel
- // 是否共线 / 平行
- {
- return dcmp(cross(a,b))==0;
- }
- Point pointline(const Point& p,const Point& a,const Vec& v)
- // 点在直线上投影, GetLineProjection
- {
- return a+v*(dot(p-a,v)/dot(v,v));
- }
- bool ifsegseg(const Point& a1,const Point& a2,const Point& b1,const Point& b2)
- //SegmentProperIntersection, 线段相交判定, 不包含端点, 不允许共线有交点时求交点直接用直线交点即可
- // 此处就是求两条线段的两个端点是否都分别在另一条线段的两侧
- {
- double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1),
- c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
- return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
- }
- bool ifonseg(const Point& p,const Point& a1,const Point& a2)
- //OnSegment, 点是否在线段上, 不含端点
- // 这样就能判定向量 p a1 与 p a2 共线, 且方向相反
- {
- return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
- }
- bool ifonseg1(const Point& p,const Point& a1,const Point& a2)
- // 点是否在线段上, 含端点
- {
- return (dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0)||p==a1||p==a2;
- }
- bool ifsegseg1(const Point& a1,const Point& a2,const Point& b1,const Point& b2)
- // 线段相交判定, 包含端点, 允许共线
- {
- double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1),
- c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
- return (dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0)
- ||ifonseg(a1,b1,b2)//(dcmp(c1)==0&&dcmp(c2)==0)||
- ||ifonseg(a2,b1,b2)||ifonseg(b1,a1,a2)||ifonseg(b2,a1,a2)
- ||a1==b1||a1==b2||a2==b1||a2==b2;
- }
- double polyarea(Point p[],int n)
- //PolygonArea, 有向面积, 要求点按顺序能组成多边形 (不会边相交, 可以凹), 如果顺时针转就是负, 逆时针就是正 (未验证)
- {
- double ans=0;
- for(int i=1;i<n-1;i++)
- ans+=cross(p[i]-p[0],p[i+1]-p[0]);
- return ans/2;
- }
- };
- using namespace X;
- int main()
- {
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2504335.html