計算幾何模板：

#include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const double eps = 1e-8; int sgn(double x) {if(fabs(x) < eps)return 0;if(x < 0) return -1;return 1; } struct Point {double x,y;int id;Point() {}Point(double x,double y):x(x),y(y) {}Point operator -(const Point &b)const {return Point(x - b.x,y - b.y);}double operator ^(const Point &b)const {return x*b.y - y*b.x;}double operator *(const Point &b)const {return x*b.x + y*b.y;} } p[1005]; int pos,n; struct Line {Point s,e;Line() {}Line(Point s,Point e):s(s),e(e) {}pair<Point,int> operator &(const Line &b)const {Point res = s;if(sgn((s-e)^(b.s-b.e)) == 0) {if(sgn((b.s-s)^(b.e-s)) == 0)return make_pair(res,0);//兩直線重合else return make_pair(res,1);//兩直線平行}double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));res.x += (e.x - s.x)*t;res.y += (e.y - s.y)*t;return make_pair(res,2);//有交點，并返回交點} }; inline double xmult(Point p0,Point p1,Point p2) { return (p1-p0)^(p2-p0);}//p0p1 X p0p2 bool Seg_inter_line(Line l1,Line l2) { return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e)) <= 0;}//判斷直線l1和線段l2是否相交 double dist(Point a,Point b) {return sqrt((b - a)*(b - a));} bool inter(Line l1,Line l2) {//判斷線段相交returnmax(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0&&sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0; } //兩線段相交判斷 //2 規范相交 //1 非規范相交 //0 不相交 int segcrossseg(Line l1,Line l2) {int d1 = sgn((l1.e-l1.s)^(l2.s-l1.s));int d2 = sgn((l1.e-l1.s)^(l2.e-l1.s));int d3 = sgn((l2.e-l2.s)^(l1.s-l2.s));int d4 = sgn((l2.e-l2.s)^(l1.e-l2.s));if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;return (d1==0 && sgn((l2.s-l1.s)*(l2.s-l1.e))<=0) ||(d2==0 && sgn((l2.e-l1.s)*(l2.e-l1.e))<=0) ||(d3==0 && sgn((l1.s-l2.s)*(l1.s-l2.e))<=0) ||(d4==0 && sgn((l1.e-l2.s)*(l1.e-l2.e))<=0); } //直線和線段相交判斷 //-*this line -v seg //2 規范相交 //1 非規范相交 //0 不相交 int linecrossseg(Line l1,Line l2) {//l1直線，l2線段 int d1 = sgn((l1.e-l1.s)^(l2.s-l1.s));int d2 = sgn((l1.e-l1.s)^(l2.e-l1.s));if((d1^d2)==-2) return 2;return (d1==0||d2==0); }

注意：

使用反三角函數時，要注意定義域的范圍，比如，經過計算 x = 1.000001double x = 1.000001; double acx = acos(x); //可能會返回runtime error//此時我們可以加一句判斷 double x = 1.000001; if(fabs(x - 1.0) < eps || fabs(x + 1.0) < eps)x = round(x); double acx = acos(x);

?

總結

以上是生活随笔為你收集整理的计算几何 模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。