整理计算几何模板，以及一些题目

 

Update 1：基础函数，点，向量的运算

Update 2：凸包，旋转卡壳

基础的函数定义

1 const double eps = 1e-8;2 int dcmp(double x) {3   if (fabs(x) < eps) return 0;4   else return x > 0 ? 1:-1;5 }

 

基于点和向量的运算

1 struct Point {  2   double x, y;  3   Point(double _x, double _y):x(_x),y(_y){}  4   Point():x(0.0),y(0.0){}  5 };  6 typedef Point Vec;  7   8 void showPoint(Point A) {  9   printf("(%.6f, %.6f)\n", A.x, A.y); 10 } 11 const Vec operator + (Vec A, Vec B) { 12   return Vec(A.x+B.x, A.y+B.y); 13 } 14 const Vec operator - (Vec A, Vec B) { 15   return Vec(A.x-B.x, A.y-B.y); 16 } 17 const double operator * (Vec A, Vec B) { 18   return A.x*B.x + A.y*B.y; 19 } 20 // A*B = |A|*|B|*sin(theta) 21 // theta为 A,B 向量的夹角 22 // 如果 A 在 B 的顺时针方向180度内，则theta取正值 23 // 向量叉乘 24 // 返回值为正时，表示 A 在 B 的右侧180度内 25 // 返回值的绝对值等于以A,B向量为邻边的平行四边型的面积 26 const double operator ^ (Vec A, Vec B) { 27   return A.x*B.y - A.y*B.x; 28 } 29  30 double Lenth(Vec &v) { 31     return sqrt(v*v); 32 } 33  34  35 // 将点 A 绕 p 逆时针旋转 theta 角度(弧度制) 36 // 1.平移坐标 37 // 2.旋转 38 // 3.平移坐标 39 Vec rotate(point A, point p， double theta) { 40     A = A-p; 41     point ret = point(A.x*cos(theta)-A.y*sin(theta), A.x*sin(theta)+A.y*cos(theta)) + p; 42     return ret; 43 } 44  45  46 // 计算C到AB的距离 47 // isSeg = 1 : AB为线段 48 // isSeg = 0 : AB为直线 49 double linePointDist(Point A, Point B, Point C, bool isSeg) { 50   double dist = ((B-A)^(C-A)) / sqrt((B-A)*(B-A)); 51   if (isSeg) { 52     double dot1 = (C-B)*(B-A); 53     if (dot1 > 0) return sqrt((B-C)*(B-C)); 54     double dot2 = (C-A)*(A-B); 55     if (dot2 > 0) return sqrt((A-C)*(A-C)); 56   } 57   return fabs(dist); 58 } 59  60 // 判断线段的两个端点是否在直线的两侧 61 bool lineCrossSeg(Point p1, Point p2, Point ls, Point le) 62 { 63   Vec ver = ls-le, v1 = p1-ls, v2 = p2-ls; 64   return dcmp((ver^v1)*(ver^v2)) <= 0; 65 } 66  67 // 判断点是否在线段上 68 // 叉积为 0 表示共线 69 bool pointOnSeg(point s1, point s2, point p, bool includeEnd) 70 { 71   if ((s1 == p || s2 == p) && !includeEnd) return false; 72   s2 = s2-s1; 73   p = p-s1; 74   return (s2^p)==0 && (s2*p)>=0; 75  76   double minx = min(s1.x, s2.x); 77   double maxx = max(s1.x, s2.x); 78   double miny = min(s1.y, s2.y); 79   double maxy = max(s1.y, s2.y); 80  81   if ((s1 == p || s2 == p) && !includeEnd) return false; 82   if (p.x-minx>=0  83       && maxx-p.x>=0  84       && p.y-miny>=0  85       && maxy-p.y>=0 86       && ((s2-s1)^(p-s1)) == 0) 87     return true; 88   else 89     return false; 90 } 91  92  93 // 判断两条线段是否相交 94 // 两次跨立试验 95 typedef pair
      
        seg; 96 bool segCrossSeg(seg a, seg b, bool includeEnd) 97 { 98   Vec ver = b.X-b.Y, v1 = a.X-b.X, v2 = a.Y-b.X; 99   int tmp1 = dcmp((ver^v1)*(ver^v2));100   ver = a.X-a.Y, v1 = b.X-a.X, v2 = b.Y-a.X;101   int tmp2 = dcmp((ver^v1)*(ver^v2));102   if (includeEnd)103     return tmp1 <= 0 && tmp2 <= 0;104   else105     return tmp1 < 0 && tmp2 < 0;106 }107 108 double areaPoly(vector
       
         &P) {109   double area = 0.0;110   for (int i = 1, n = P.size(); i+1 < n; i++) {111     area += (P[i+1]-P[0])^(P[i]-P[0]);112   }113   return area / 2.0;114 }
       
      

 

基于直线的运算（直线方程 : Ax+By=C）

1 struct Line { 2   // Ax + By = C 3   double A, B, C; 4   Line(double _A, double _B, double _C):A(_A),B(_B),C(_C){} 5   Line():A(0.0),B(0.0),C(0.0){} 6 }; 7  8 Line getLineFromPoints(Point p1, Point p2) { 9   double A = p2.y-p1.y;10   double B = p1.x-p2.x;11   double C = A*p1.x + B*p1.y;12   return Line(A,B,C);13 }14 15 // int = 0 无交点16 // int = 1 一个交点17 // int = 2 两直线重合18 pair
      
        intersectPoint(Line l1, Line l2) {19   double det = l1.A*l2.B - l2.A*l1.B;20   if (dcmp(det) == 0) {21     // 两直线平行 重合22     if (dcmp(l1.A*l2.C - l2.A*l1.C) == 0 &&23         dcmp(l1.B*l2.C - l2.B*l1.C) == 0)24     return make_pair(Point(), 2);25     else26       return make_pair(Point(), 0);27   }28   else {29     double x = (l2.B*l1.C - l1.B*l2.C) / det;30     double y = (l1.A*l2.C - l2.A*l1.C) / det;31     return make_pair(Point(x,y), 1);32   }33 }
      

 

凸包模板（白书）

1 bool cmpxy(point a, point b) 2 { 3   if (a.x == b.x) return a.y < b.y; 4   return a.x < b.x; 5 } 6 // 包含边上的点就将 <= 改为 < 7 int convexHull(Point *p, int n) 8 { 9   sort(p, p + n, cmpxy);10   int top = 0;11   for (int i = 0; i < n; i++)12   {13     while(top>1 && ((p[s[top-1]]-p[s[top-2]])^(p[i]-p[s[top-2]])) <= 0) top--;14     s[top++] = i;15   }16   int k = top;17   for (int i=n-2;i>=0;i--)18   {19     while(top>k && ((p[s[top-1]]-p[s[top-2]])^(p[i]-p[s[top-2]])) <= 0) top--;20     s[top++] = i;21   }22   if (n > 1) top--;23   return top;24 }

 

旋转卡壳

1 // s 为保存有序的凸包点的下标的栈 2 // 此处的凸包点为顺时针的顺序 3 int rotatingCaliper(Point *p, int top) 4 { 5   int q = 1; 6   int ans = 0; 7   s[top] = 0; 8   for (int i = 0; i < top; i++) 9   {10     while( ((p[s[i+1]]-p[s[i]])^(p[s[q+1]]-p[s[i]])) > 11            ((p[s[i+1]]-p[s[i]])^(p[s[q]]  -p[s[i]])) )12       q = (q+1)%top;13     ans = max(ans, (p[s[i]]-p[s[q]])*(p[s[i]]-p[s[q]]));14     // 处理两条边平行的情况15     ans = max(ans, (p[s[i+1]]-p[s[q+1]])*(p[s[i+1]]-p[s[q+1]]));16   }17   return ans;18 }