1 struct vector2 {3    double x,y;4    vector (double X=0,double Y=0)5    {6        x=X,y=Y;7     }8 }9 typedef vector point;

 

向量四则运算

1 vector operator + (vector a,vector b)  {
   return vector (a.x+b.x,a.y+b.y); }2 vector operator - (vector a,vector b)   {
   return vector (a.x-b.x,a.y-b.y);}3 vector operator *  (vector a,double p)  {
   return vector (a.x*p,a.y*p);}4 vector operator /  (vector a.double p){
   return vector (a.x/p,a.y/p);}

 

精度控制

1 const double eps=1e-8;2 int dcmp(double x)3 {4     if (fabs(x)

 

求a向量的长度

1 double len(vector a)2 {3     return sqrt(a.x*a.x+a.y*a.y)4 }

 

点积

a·b的几何意义为a在b上的投影长度乘以b的模长

a·b=|a||b|cosθ,其中θ为a,b之间的夹角

坐标表示

a=(x1,y1) b=(x2,y2)

a·b=x1*x2+y1*y2;

1 double dot(vector a,vector b)2 {3     return a.x*b.x+a.y*b.y;4 }

 

两个向量的叉积是一个标量，a×b的几何意义为他们所形成的平行四边形的有向面积

坐标表示a=(x1,y1) b=(x2,y2)

a×b=x1y2-x2y1

1 double cross(vector a,vector b)2 {3     return a.x*b.y-a.y*b.x;4 }

 

点、直线、线段的关系

点到直线的距离

利用叉积求面积，然后除以平行四边形的底边长，得到平行四边形的高即点到直线的距离

1 double distl(point p,point a,point b)2 {3     vector v=p-a; vector u=b-a;4     return fabs(cross(v,u))/len(u);5 }

点到线段的距离

比点到直线的距离稍微复杂。因为是线段，所以如果平行四边形的高在区域之外的话就不合理，这时候需要计算点到距离较近的端点的距离

1 double dists(point p,point a,point b)2 {3     if (a==b) return len(p-a);4     vector v1=b-a,v2=p-a,v3=p-b;5     if (dcmp(dot(v1,v2))<0) return len(v2);6     else if (dcmp(dot(v1,v3))>0) return len(v3);7     return fabs(cross(v1,v2))/len(v1);8 }

 

判断两个线段是否相交

跨立实验：判断一条线段的两端是否在另一条线段的两侧（两个端点与另一线段的叉积乘积为负）。需要正反判断两侧

1 bool segment(point a,point b,point c,point d)2 {3     double c1=cross(b-a,c-a),c2=cross(b-a,d-a);4     double d1=cross(d-c,a-c),d2=cross(d-c,b-c);5     return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;6 }

 

求两条直线的交点

1 point line_intersection(point a,point a0,point b,point b0)   2 {   3     double a1,b1,c1,a2,b2,c2;   4     a1 = a.y - a0.y;   5     b1 = a0.x - a.x;   6     c1 = cross(a,a0);   7     a2 = b.y - b0.y;   8     b2 = b0.x - b.x;   9     c2 = cross(b,b0);  10     double d = a1 * b2 - a2 * b1;  11     return point((b1 * c2 - b2 * c1) / d,(c1 * a2 - c2 * a1) / d);  12 }

 

多边形相关 判断点在多边形内部

射线法：以该点为起点引一条射线，与多边形的边界相交奇数次，说明在多边形的内部

1 int pointin(point p,point* a,int n)    2 {   3     int wn=0,k,d1,d2;   4     for (int i=1;i<=n;i++)   5     {   6         if (dcmp(dists(p,a[i],a[(i+1-1)%n+1]))==0)  return -1;//判断点是否在多边形的边界上    7         k=dcmp(cross(a[(i+1-1)%n+1]-a[i],p-a[i]));   8         d1=dcmp(a[i].y-p.y);   9         d2=dcmp(a[(i+1-1)%n+1].y-p.y);  10         if (k>0&&d1<=0&&d2>0)  wn++;  11         if (k<0&&d2<=0&&d1>0)  wn--;  12     }  13     if (wn)  return 1;  14     else return 0;  15 }

 

求多边形的面积

1 double PolygonArea(Point* p,int n)2 {3     double area=0;4     for(int i=1;i