【计算几何】基础几何
NanoApe
posted @ 2016年2月17日 18:17
in 蒟蒻不撕烤智熵何来
, 1107 阅读
基础定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | //圆周率#define Pi acos(-1)//结构体-点struct Point{double x, y;};//结构体-线struct line{double a, b, c;};//逆时针旋转向量（弧度）Point Rotate(Point a, double rad){return (Point){a.x*cos(rad)-a.y*sin(rad), a.x*sin(rad)+a.y*cos(rad)};}//叉积，a*b>0表示向量b在向量a的左边double operator * (Point a, Point b){return a.x*b.y-a.y*b.x;}//向量求极角atan2(b.y-a.y, b.x-a.x) |
半平面交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | sort(l+1, l+m+1); //极角排序cnt=0; rep(i, 1, m){ if (l[i].ang!=a[cnt].ang) cnt++; a[cnt]=l[i];} //极角排重L=1, R=0; q[++R]=a[1]; q[++R]=a[2];rep(i, 3, cnt){ while (L<R && jud(q[R-1], q[R], a[i])) R--; while (L<R && jud(a[i], q[L], q[L+1])) L++; q[++R]=a[i];}while (L<R && jud(q[R-1], q[R], q[L])) R--;while (L<R && jud(q[R], q[L], q[L+1])) L++; |
凸包
1 2 3 4 5 6 7 8 9 10 11 12 | int k=1;rep(i, 2, n) if (p[i].y<p[k].y || (p[i].y==p[k].y && p[i].x<p[k].x)) k=i;swap(p[1], p[k]); //先把横纵坐标最小的点移至第一sort(p+2, p+n+1, cmp); //所有点顺时针排列，相同角度时按距离从小到大排s[++top]=p[1]; s[++top]=p[2];rep(i, 3, n){ while (top>1 && (p[i]-s[top-1])*(s[top]-s[top-1])<=0) top--; s[++top]=p[i];} |
动态加点维护凸包
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | //点按照横纵坐标排序set<P>::iterator r=q.lower_bound(p), l=r, t; l--;if ((*r-*l)*(p-*l)<0) return;now-=dis(*l, *r);while (1){ t=r++; if (r==q.end()) break; if ((*r-p)*(*t-p)>0) break; now-=dis(*t, *r); q.erase(t);}while (l!=q.begin()){ t=l--; if ((*t-p)*(*l-p)>0) break; now-=dis(*t, *l); q.erase(t);}q.insert(p); l=r=q.find(p); l--; r++; |
圆
圆心角θ所对弓形面积：S=12r2(θ−sin(θ))（部分圆减去三角形部分）
圆交
四种情况：相离相切、相交且两圆心分居公共弦两侧、相交且两圆心位于公共弦一侧、包含
半平面交
Step1：将所有半平面按极角排序，对于极角相同的，选择性的保留一个
Step2：使用一个双端队列，加入最开始2个半平面
Step3：每次考虑一个新的半平面：
a.假如队列顶端的两个半平面的交点在当前半平面外，删除deque顶端的半平面
b.假如队列底部的两个半平面的交点在当前半平面外，删除deque底部的半平面
c.将新半平面加入队列顶端
Step4：删除两端多余的半平面：
a.假如队列顶端的两个半平面的交点在底部半平面外，删除deque顶端的半平面
b.假如队列底部的两个半平面的交点在顶端半平面外，删除deque底部的半平面
Step5：计算出deque顶端和底部的交点即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #define eps 1e-8int n, x[maxn], y[maxn];struct node{int x1,y1,x2,y2; ld a;} k[maxn], q[maxn], g[maxn]; int L, R, tot; bool fg;struct P{ld x,y;} p[maxn];inline bool Right(node a, P b){return (b.y-a.y1)*(a.x2-a.x1)-(b.x-a.x1)*(a.y2-a.y1)<0;}inline P cross(node a, node b){ ld a1=a.y2-a.y1, b1=a.x1-a.x2, c1=1LL*a.x2*a.y1-1LL*a.x1*a.y2; ld a2=b.y2-b.y1, b2=b.x1-b.x2, c2=1LL*b.x2*b.y1-1LL*b.x1*b.y2; if (fabs(fabs(a.a-b.a)-atan2(0,-1))<eps) fg=true; // fg为true时答案为空集 return (P){(b1*c2-b2*c1)/(a1*b2-a2*b1),(a1*c2-a2*c1)/(b1*a2-b2*a1)};}bool cmp(node a, node b) {return a.a>b.a;}int main(){ //........ rep(i, 1, n) k[i]=(node){x[i],y[i],x[i+1],y[i+1],atan2(y[i+1]-y[i],x[i+1]-x[i])}; sort(k+1, k+1+n, cmp); g[tot=1]=k[1]; rep(i, 2, n) if (k[i-1].a-k[i].a>eps) g[++tot]=k[i]; else if (Right(g[tot],(P){(ld)k[i].x1,(ld)k[i].y1})) g[tot]=k[i]; L=1, R=0, q[++R]=g[1], q[++R]=g[2]; rep(i, 3, tot) { while (L<R && !Right(g[i],cross(q[R],q[R-1]))) R--; while (L<R && !Right(g[i],cross(q[L],q[L+1]))) L++; q[++R]=g[i]; } while (L<R && !Right(q[L],cross(q[R],q[R-1]))) R--; while (L<R && !Right(q[R],cross(q[L],q[L+1]))) L++; //........ return 0;} |
评论 (0)
