二维计算几何模板

2018-06-17 22:03:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

//参考的刘汝佳老师

1
#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #define Vector Point 6 using namespace std; 7 inline void read(int &n) 8 { 9 char c='+';bool flag=0;n=0; 10 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 11 while(c>='0'&&c<='9') n=n*10+(c-48),c=getchar(); 12 if(flag==1)n=-n; 13 } 14 const double PI=acos(-1); 15 const double eps=1e-10; 16 int dcmp(double x) {return (fabs(x)<eps)?0:(x<0?-1:1);} 17 struct Point 18 { 19 double x,y; 20 Point(double x=0,double y=0):x(x),y(y){}; 21 }; 22 Vector operator + (Vector A,Vector B) {return Vector(A.x + B.x,A.y + B.y);} 23 Vector operator - (Vector A,Vector B) {return Vector(A.x - B.x,A.y - B.y);} 24 Vector operator * (Vector A,double P) {return Vector(A.x * P,A.y * P);} 25 Vector operator / (Vector A,double P) {return Vector(A.x / P,A.y / P);} 26 bool operator < (const Point &a,const Point &b){return a.x < b.x || (a.x == b.x && a.y < b.y);} 27 bool operator == (const Point &a,const Point &b){return dcmp(a.x - b.x)==0 && dcmp(a.y - b.y)==0;} 28 29 double Dot(Vector A,Vector B){return A.x * B.x + A.y * B.y;}//点积 30 double Length(Vector A){return sqrt(Dot(A,A));}// 求向量的长度 31 double Angle(Vector A,Vector B){return acos(Dot(A,B) / (Length(A)) / Length(B));} //求两个向量的夹角 32 33 double Cross(Vector A,Vector B){return A.x * B.y-A.y * B.x;}// 两个向量的叉积 34 double Area2(Point A,Point B,Point C){return Cross(B - A,C - A);} 35 36 Vector Rotate(Vector A,double rad){return Vector(A.x * cos(rad)-A.y * sin(rad),A.x * sin(rad)+A.y * cos(rad));}// 向量旋转 37 38 Point GetLineIntersection(Point P,Point v,Point Q,Point w)// 两直线的交点 **************** 39 { 40 Vector u=P-Q; 41 double t=Cross(w,u)/Cross(v,w); 42 return P+v*t; 43 } 44 45 double DistanceToLine(Point P,Point A,Point B)// 点P到直线AB的距离 46 { 47 Vector v1=B - A;Vector v2= P-A; 48 return fabs(Cross(v1,v2)) / Length(v1); 49 } 50 51 double DistanceToSegment(Point P,Point A,Point B)// 点P到线段AB的距离 52 { 53 if(A==B) return Length(P-A); 54 Vector v1=B-A, v2=P-A, v3=P-B; 55 if(dcmp(Dot(v1,v2)) < 0) return Length(v2); 56 else if(dcmp(Dot(v1,v3)) > 0) return Length(v3);// 怎么会是大于。。。。。。 57 else return fabs(Cross(v1,v2)) / Length(v1); 58 } 59 60 Point GetLineProjection(Point P, Point A, Point B)// 求点P在直线AB上的正投影 61 { 62 Vector v=B-A; 63 return A+v*(Dot(v, P-A) / Dot(v,v)); 64 } 65 66 bool SegmentProperIntersection(Point a1, Point a2, Point b1,Point b2)//判断两线段是否相交 67 { 68 double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1), 69 c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1); 70 return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; 71 } 72 bool OnSegment(Point p,Point a1,Point a2) 73 { 74 return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p)) < 0; 75 } 76 double PolygonArae(Point *p,int n)// 求多边形的有向面积 77 { 78 double area = 0; 79 for(int i=1;i<=n-1;i++) 80 area += Cross(p[i]-p[0],p[i+1]-p[0]); 81 return area/2; 82 } 83 Point read_point() 84 { 85 double x,y; 86 scanf("%lf%lf",&x,&y); 87 return Point(x,y); 88 } 89 int main() 90 { 91 92 return 0; 93 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:[SinGuLaRiTy] 树链问题

下一篇:P1429 平面最近点对(加强版)