2018-2-23改
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 namespace X 5 { 6 const double eps=1e-10; 7 struct Point 8 { 9 double x,y; 10 Point(double x=0,double y=0):x(x),y(y){} 11 }; 12 typedef Point Vec; 13 Vec operator+(const Vec& a,const Vec& b) 14 { 15 return Vec(a.x+b.x,a.y+b.y); 16 } 17 Vec operator-(const Vec& a,const Vec& b) 18 { 19 return Vec(a.x-b.x,a.y-b.y); 20 } 21 Vec operator*(const double& a,const Vec& b) 22 { 23 return Vec(a*b.x,a*b.y); 24 } 25 Vec operator*(const Vec& a,const double& b) 26 { 27 return Vec(b*a.x,b*a.y); 28 } 29 Vec operator/(const Vec& a,const double& b) 30 { 31 return Vec(a.x/b,a.y/b); 32 } 33 int dcmp(double x) 34 //正为1，负为-1，0为0 35 { 36 if(fabs(x)<eps) return 0; 37 return x<0?-1:1; 38 } 39 bool operator==(const Vec& a,const Vec& b) 40 //判向量相等 41 { 42 return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; 43 } 44 double dot(const Vec& a,const Vec& b) 45 //点积 46 { 47 return a.x*b.x+a.y*b.y; 48 } 49 double cross(const Vec& a,const Vec& b) 50 //叉积 51 { 52 return a.x*b.y-a.y*b.x; 53 } 54 double len(const Vec& x) 55 //向量长度 56 { 57 return sqrt(dot(x,x)); 58 } 59 double angle(const Vec& a,const Vec& b) 60 //夹角，0~180° 61 { 62 return acos(dot(a,b)/len(a)/len(b)); 63 } 64 double angle1(const Vec& a,const Vec& b) 65 //夹角，带方向，a到b逆时针为正，顺时针为负，共线为0 66 { 67 return acos(dot(a,b)/len(a)/len(b))*(dcmp(cross(a,b))); 68 } 69 Vec rotate(const Vec& a,const double& rad) 70 //旋转，正为逆时针，负为顺时针 71 { 72 return Vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad)); 73 } 74 Vec normal(const Vec& x) 75 //单位法线，左转90°后除以自身长度 76 { 77 double l=len(x); 78 return Vec(-x.y/l,x.x/l); 79 } 80 Vec normal1(const Vec& x) 81 //法线，不归一化 82 { 83 return Vec(-x.y,x.x); 84 } 85 Point lineline(const Point& p,const Vec& v,const Point& q,const Vec& w) 86 //直线交点,GetLineIntersection 87 { 88 return p+v*cross(w,p-q)/cross(v,w); 89 } 90 double ptline(const Point& p,const Point& a,const Point& b) 91 //point_to_line,点到直线距离,DistanceToLine 92 { 93 Vec v1=b-a,v2=p-a; 94 return fabs(cross(v1,v2)/len(v1)); 95 } 96 double ptseg(const Point& p,const Point& a,const Point& b) 97 //point_to_segment,点到线段距离,DistanceToSegment 98 { 99 if(a==b) return len(p-a); 100 //Vec v1=b-a,v2=a-p,v3=p-b; 101 Vec v1=b-a,v2=p-a,v3=p-b; 102 if(dcmp(dot(v1,v2))<0) return len(v2); 103 else if(dcmp(dot(v1,v3))>0) return len(v3); 104 else return fabs(cross(v1,v2)/len(v1)); 105 } 106 double area2(const Point& a,const Point& b,const Point& c) 107 //叉积对应平行四边形的面积 108 { 109 return cross(b-a,c-a); 110 } 111 double thrarea(const Point& a,const Point& b,const Point& c) 112 //三角形面积，绝对值 113 { 114 return fabs(cross(b-a,c-a)/2); 115 } 116 bool ifpar(const Vec& a,const Vec& b) 117 //ifParallel 118 //是否共线/平行 119 { 120 return dcmp(cross(a,b))==0; 121 } 122 Point pointline(const Point& p,const Point& a,const Vec& v) 123 //点在直线上投影,GetLineProjection 124 { 125 return a+v*(dot(p-a,v)/dot(v,v)); 126 } 127 bool ifsegseg(const Point& a1,const Point& a2,const Point& b1,const Point& b2) 128 //SegmentProperIntersection,线段相交判定，不包含端点，不允许共线。有交点时求交点直接用直线交点即可 129 //此处就是求两条线段的两个端点是否都分别在另一条线段的两侧 130 { 131 double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1), 132 c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1); 133 return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0; 134 } 135 bool ifonseg(const Point& p,const Point& a1,const Point& a2) 136 //OnSegment,点是否在线段上，不含端点 137 //这样就能判定向量p a1与p a2共线，且方向相反 138 { 139 return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0; 140 } 141 bool ifonseg1(const Point& p,const Point& a1,const Point& a2) 142 //点是否在线段上，含端点 143 { 144 return (dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0)||p==a1||p==a2; 145 } 146 bool ifsegseg1(const Point& a1,const Point& a2,const Point& b1,const Point& b2) 147 //线段相交判定，包含端点，允许共线 148 { 149 double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1), 150 c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1); 151 return (dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0) 152 ||ifonseg(a1,b1,b2)//(dcmp(c1)==0&&dcmp(c2)==0)|| 153 ||ifonseg(a2,b1,b2)||ifonseg(b1,a1,a2)||ifonseg(b2,a1,a2) 154 ||a1==b1||a1==b2||a2==b1||a2==b2; 155 } 156 double polyarea(Point p[],int n) 157 //PolygonArea,有向面积，要求点按顺序能组成多边形（不会边相交，可以凹），如果顺时针转就是负，逆时针就是正（未验证） 158 { 159 double ans=0; 160 for(int i=1;i<n-1;i++) 161 ans+=cross(p[i]-p[0],p[i+1]-p[0]); 162 return ans/2; 163 } 164 }; 165 using namespace X; 166 int main() 167 { 168 169 return 0; 170 }