尽管才刚入门 然而最近各方面能力都在下降 还是先把这个计算几何入门级模板放上来 弃坑做点其他的
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 const double eps = 1e-8, inf = 1e8, pi = acos(-1); 7 const int N = 110; 8 struct point 9 { 10 double x, y; 11 point(double _x = 0, double _y = 0) 12 { 13 x = _x; 14 y = _y; 15 } 16 point operator - (const point &p) const 17 { 18 return point(x - p.x, y - p.y); 19 } 20 point operator + (const point &p) const 21 { 22 return point(x + p.x, y + p.y); 23 } 24 double operator * (const point &p) const 25 { 26 return x * p.y - y * p.x; 27 } 28 double operator / (const point &p) const 29 { 30 return x * p.x + y * p.y; 31 } 32 }a[N], b[N << 1]; 33 struct line 34 { 35 point p1, p2; 36 double ang; 37 void getang() 38 { 39 ang = atan2(p2.y - p1.y, p2.x - p1.x); 40 } 41 }c[N], q[N]; 42 int n; 43 bool cmp(const point &aa, const point &bb) 44 { 45 return aa.x < bb.x || (aa.x == bb.x && aa.y < bb.y); 46 } 47 bool cmpl(const line &aa, const line &bb) 48 { 49 if(abs(aa.ang - bb.ang) > eps) 50 return aa.ang < bb.ang; 51 return (bb.p2 - aa.p1) * (bb.p1 - bb.p2) > 0; 52 } 53 int sgn(double x) 54 //正负判断 55 { 56 if(x > eps) 57 return 1; 58 if(x < -eps) 59 return -1; 60 return 0; 61 } 62 double getdist2(const point &aa) 63 { 64 return (aa.x * aa.x + aa.y * aa.y); 65 } 66 bool online(const point &aa, const point &bb, const point &cc) 67 //三点共线判断 68 { 69 if(!(min(bb.x, cc.x) <= aa.x && aa.x <= max(bb.x, cc.x))) 70 return 0; 71 if(!(min(bb.y, cc.y) <= aa.y && aa.y <= max(bb.y, cc.y))) 72 return 0; 73 return !sgn((bb - aa) * (cc - aa)); 74 } 75 bool checkline(const point &aa, const point &bb, const point &cc, const point &dd) 76 //线段是否相交 77 { 78 int c1 = sgn((bb - aa) * (cc - aa)), c2 = sgn((bb - aa) * (dd - aa)), 79 c3 = sgn((dd - cc) * (aa - cc)), c4 = sgn((dd - cc) * (bb - cc)); 80 if(c1 * c2 < 0 && c3 * c4 < 0) 81 return 1;//规范相交 82 if(c1 == 0 && c2 == 0) 83 { 84 if(min(aa.x, bb.x) > max(cc.x, dd.x) || min(cc.x, dd.x) > max(aa.x, bb.x) 85 || min(aa.y, bb.y) > max(cc.y, dd.y) || min(cc.y, dd.y) > max(aa.y, bb.y)) 86 return 0; 87 return 1;//共线有重叠 88 } 89 if(online(cc, aa, bb) || online(dd, aa, bb) 90 || online(aa, cc, dd) || online(bb, cc, dd)) 91 return 1;//端点相交 92 return 0; 93 } 94 point getpoint(const point &aa, const point &bb, 95 const point &cc, const point &dd) 96 //两直线交点 97 { 98 double a1, b1, c1, a2, b2, c2; 99 point re; 100 a1 = aa.y - bb.y; 101 b1 = bb.x - aa.x; 102 c1 = aa * bb; 103 a2 = cc.y - dd.y; 104 b2 = dd.x - cc.x; 105 c2 = cc * dd; 106 //以下为交点横纵坐标 107 re.x = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2); 108 re.y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1); 109 return re; 110 } 111 bool protrusion(point aa[]) 112 //判断多边形凹(凸) 113 { 114 int flag = sgn((aa[1] - aa[0]) * (aa[2] - aa[0])); 115 for(int i = 1; i < n; ++i) 116 if(sgn((aa[(i + 1) % n] - aa[i]) * (aa[(i + 2) % n] - aa[i])) != flag) 117 return 1; 118 return 0; 119 } 120 bool inpolygon(const point &aa) 121 //点在凸多边形内(外) 122 { 123 int flag = sgn((a[0] - aa) * (a[1] - aa)); 124 for(int i = 1; i < n; ++i) 125 if(sgn((a[i] - aa) * (a[(i + 1) % n] - aa)) != flag) 126 return 0; 127 return 1; 128 } 129 void transline(line &aa, double dist) 130 //逆时针方向平移线段 131 { 132 double d = sqrt((aa.p1.x - aa.p2.x) * (aa.p1.x - aa.p2.x) + 133 (aa.p1.y - aa.p2.y) * (aa.p1.y - aa.p2.y)); 134 point ta; 135 ta.x = aa.p1.x + dist / d * (aa.p1.y - aa.p2.y); 136 ta.y = aa.p1.y - dist / d * (aa.p1.x - aa.p2.x); 137 aa.p2 = ta + aa.p2 - aa.p1; 138 aa.p1 = ta; 139 } 140 void convexhull(point aa[], point bb[]) 141 //凸包 142 { 143 int len = 0; 144 sort(aa, aa + n, cmp); 145 bb[len++] = aa[0];//bb数组要开2倍(防止出现直线) 146 bb[len++] = aa[1]; 147 for(int i = 2; i < n ;++i) 148 { 149 while(len > 1 && (aa[i] - bb[len - 2]) * (bb[len - 1] - bb[len - 2]) > 0) 150 //若严格则加上等于 151 --len; 152 bb[len++] = aa[i]; 153 } 154 int t = len; 155 for(int i = n - 2; i >= 0; --i) 156 { 157 while(len > t && (aa[i] - bb[len - 2]) * (bb[len - 1] - bb[len - 2]) > 0) 158 //同上 159 --len; 160 bb[len++] = aa[i]; 161 } 162 --len; 163 n = len; 164 } 165 bool checkout(const line &aa, const line &bb, const line &cc) 166 //检查交点是否在向量顺时针侧 167 { 168 point p = getpoint(aa.p1, aa.p2, bb.p1, bb.p2); 169 return (cc.p1 - p) * (cc.p2 - p) < 0;//如果不允许共线或算面积 则此处不取等 170 } 171 double halfplane(point aa[], line bb[]) 172 //半平面交 173 { 174 sort(bb, bb + n, cmpl); 175 int n2 = 1; 176 for(int i = 1; i < n; ++i) 177 { 178 if(bb[i].ang - bb[i - 1].ang > eps) 179 ++n2; 180 bb[n2 - 1]= bb[i]; 181 } 182 n = n2; 183 int front = 0, tail = 0; 184 q[tail++] = bb[0], q[tail++] = bb[1]; 185 for(int i = 2; i < n; ++i) 186 { 187 while(front + 1 < tail && checkout(q[tail - 2], q[tail - 1], bb[i])) 188 --tail; 189 while(front + 1 < tail && checkout(q[front], q[front + 1], bb[i])) 190 ++front; 191 q[tail++] = bb[i]; 192 } 193 while(front + 2 < tail && checkout(q[tail - 2], q[tail - 1], q[front])) 194 --tail; 195 while(front + 2 < tail && checkout(q[front], q[front + 1], q[tail - 1])) 196 ++front; 197 if(front + 2 >= tail) 198 return 0; 199 int j = 0; 200 for(int i = front; i < tail; ++i, ++j) 201 { 202 aa[j] = getpoint(q[i].p1, q[i].p2, q[(i != tail - 1 ? i + 1 : front)].p1, 203 q[(i != tail - 1 ? i + 1 : front)].p2); 204 } 205 double re = 0; 206 for(int i = 1; i < j - 1; ++i) 207 re += (aa[i] - aa[0]) * (aa[i + 1] - aa[0]); 208 return abs(re * 0.5); 209 } 210 double calipers(point aa[]) 211 //旋转卡壳 212 { 213 double re = 0; 214 aa[n] = aa[0]; 215 int now = 1; 216 for(int i = 0; i < n; ++i) 217 { 218 while((aa[i + 1] - aa[i]) * (aa[now + 1] - aa[i]) > 219 (aa[i + 1] - aa[i]) * (aa[now] - aa[i])) 220 now = (now == n - 1 ? 0 : now + 1); 221 re = max(re, getdist2(aa[now] - aa[i])); 222 } 223 return re; 224 } 225 line bisector(const point &aa, const point &bb) 226 //中垂线(正方形) 227 { 228 double mx, my; 229 mx = (aa.x + bb.x) / 2; 230 my = (aa.y + bb.y) / 2; 231 line cc; 232 cc.p1.x = mx - (aa.y - bb.y) / 2; 233 cc.p1.y = my + (aa.x - bb.x) / 2; 234 cc.p2 = aa + bb - cc.p1; 235 cc.getang(); 236 return cc; 237 } 238 //皮克定理 ans = s - point / 2 + 1 239 int main() 240 { 241 242 return 0; 243 }
原文：http://www.cnblogs.com/sagitta/p/5324123.html