首页 > 代码库 > 【计算几何】基础总结+题目推荐
【计算几何】基础总结+题目推荐
刷了很久计算几何，好歹算是有些收获，总结一下吧。
计算几何不同与解析几何，这里大部分使用的是向量和点，而不是解析式。
直线/射线：一个点+一个方向向量。
线段：两个端点。
多边形：按逆时针排序的点集。
圆：圆心+半径。
点积：两个向量的数量积。
叉积：两个向量组成的四边形的有向面积。
基础部分有这些差不多了。比起解析式的运算过程来说，向量法的误差要小很多，而且基本不需要考虑特殊情况。
下面举个例子吧，分析解析几何和计算几何的差别。
最普通的，判断两直线是否相交或者重合，如果相交就计算交点。
解析法：通过给定的四个点分别计算出每条直线的解析式，列二元一次方程组求解交点坐标。同时需要考虑到直线与坐标轴平行的特殊情况。
向量法：用向量法表示出两条直线，若两向量叉积为0则向量共线，直线平行或重合。
设交点P = A+tu，相当于A沿着向量走了t步，u是a直线的方向向量。既然P一定在b直线上，那么向量PC与向量v一定共线，叉积为0。解一元方程求解即可。
向量还是比较方便的。下面丢一点题目吧。
【POJ1269】
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #define eps 1e-6 7 using namespace std; 8 9 int i,j,n,m,k,T;10 11 struct node12 {13 int x,y;14 node(){}15 node(int a,int b) { x = a,y = b; }16 };17 struct line { node po,ve; }l1,l2;18 19 int cj(node a,node b) { return a.x*b.y-a.y*b.x; }20 21 void getline(line &x)22 {23 int a,b,c,d;24 scanf("%d %d %d %d",&a,&b,&c,&d);25 26 x.po = node(a,b);27 x.ve = node(c-a,d-b);28 }29 30 int main()31 {32 scanf("%d",&T);33 printf("INTERSECTING LINES OUTPUT\n");34 while (T--)35 {36 getline(l1); getline(l2);37 38 if (l1.ve.x * l2.ve.y == l1.ve.y * l2.ve.x)39 {40 node s( l1.po.x-l2.po.x , l1.po.y-l2.po.y );41 if ( cj(s,l1.ve) == 0 ) printf("LINE\n");42 else printf("NONE\n");43 }44 else{45 double fm = ( (l1.po.x-l2.po.x)*l2.ve.y - (l1.po.y-l2.po.y)*l2.ve.x );46 double fz = (l1.ve.x * l2.ve.y - l1.ve.y * l2.ve.x );47 48 double t = - fm / fz;49 50 double ansx = l1.po.x + t * l1.ve.x, ansy = l1.po.y + t * l1.ve.y;51 52 printf("POINT %.2lf %.2lf\n",ansx,ansy);53 }54 55 }56 printf("END OF OUTPUT\n");57 58 return 0;59 }上面说到的直线相交，入门题。
【POJ2318】题意：n条线段将一个矩形分成n+1块，计算每一个块内有几个点。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 7 struct node 8 { 9 int x,y;10 node(){}11 node(int a,int b) { x=a,y=b; }12 };13 struct Line{ node po,ve; } L[5005];14 int ans[5005];15 int i,j,n,m,k,x1,x2,y1,y2;16 17 int cj(node a,node b) { return a.x*b.y-a.y*b.x; }18 19 int main()20 {21 while ( scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2) != EOF )22 {23 if (n == 0) break;24 memset(ans,0,sizeof(ans));25 26 int a,b;27 for (i = 1; i <= n; i++)28 {29 scanf("%d %d",&a,&b);30 L[i].po = node(b,y2);31 L[i].ve = node(a-b,y1-y2);32 }33 34 for (i = 1; i <= m; i++)35 {36 scanf("%d %d",&a,&b);37 int l = 1, r = n + 1;38 while (l < r)39 {40 int mid = (l + r) >> 1;41 node s( a-L[mid].po.x,b-L[mid].po.y );42 if ( cj(s,L[mid].ve) > 0 ) l = mid+1;43 else r = mid;44 }45 ans[l-1]++;46 }47 48 for (i = 0; i <= n; i++) printf("%d: %d\n",i,ans[i]);49 printf("\n");50 }51 52 return 0;53 }
叉积有一个性质：用a叉积b时，若符号为正，则a在b的顺时针方向，否则在逆时针方向。
其实还是挺好做的，二分一下然后用叉积判断一下方向。O(nlogn)是可行的。
【POJ2653】题意：给定一些线段，按顺序插入然后判断最后有几条线段没有被盖住，保证答案<=1000。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <cmath> 6 using namespace std; 7 8 struct node 9 {10 double x,y;11 node() {};12 node (double a,double b) { x = a,y = b; }13 };14 struct Line { node p1,p2; int num; } L[100005];15 int empty[100005];16 int i,j,n,m,k,top;17 18 void clean()19 {20 int ntop = 0;21 for (int i = 1; i <= top; i++)22 {23 if (empty[i]) { empty[i] = 0; continue; }24 L[++ntop] = L[i];25 }26 top = ntop;27 }28 29 bool cmp(Line a,Line b) { return a.num < b.num; }30 double cj(node a,node b) { return a.x*b.y-a.y*b.x; }31 void getpoint(node &x)32 {33 double a,b;34 scanf("%lf %lf",&a,&b);35 x.x = a; x.y = b;36 }37 38 bool check(Line L1,Line L2) // L1 is a line and L2 is a segment39 {40 node s1( L2.p1.x-L1.p1.x , L2.p1.y-L1.p1.y );41 node s2( L2.p2.x-L1.p1.x , L2.p2.y-L1.p1.y );42 43 node Ex( L1.p2.x-L1.p1.x , L1.p2.y-L1.p1.y );44 45 if ( cj( s1,Ex ) * cj( s2,Ex ) > 0 ) return 0;46 return 1;47 }48 49 int main()50 {51 node a,b;52 while ( scanf("%d",&n),n != 0 )53 {54 top = 0;55 for (i = 1; i <= n; i++)56 {57 getpoint(a); getpoint(b);58 59 Line t; t.p1 = a; t.p2 = b;60 for (j = 1; j <= top; j++)61 if ( check(t,L[j]) && check(L[j],t) ) empty[j] = 1;62 63 L[++top] = t,L[top].num = i;64 if (top >= 1000) clean();65 }66 clean();67 68 sort(L+1,L+1+top,cmp);69 printf("Top sticks: %d",L[1].num);70 for (i = 2; i <= top; i++)71 printf(", %d",L[i].num);72 73 printf(".\n");74 }75 76 return 0;77 }
用一个数组维护当前在顶端的线段，每次插入一条线段的时候对于这个数组更新，若新线段能盖住某条线段则删除该条线段。
不过不知道为什么我跑得挺慢的。
【POJ1556】题意：在一个10*10的矩形中有一些墙，墙不能通过，求从（0,5）到（10,5）的最短路径。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <cmath> 6 #include <queue> 7 #define inf 1000000000 8 using namespace std; 9 10 queue<int> Q; 11 12 struct node 13 { 14 double x,y; 15 node (){} 16 node (double a,double b) { x = a, y = b; } 17 }P[10005]; 18 struct nd 19 { 20 int y,next; double c; 21 nd() {} 22 nd (int A,double B,int C) { y = A,c = B,next = C; } 23 } h[10500]; 24 struct Line { node p1,p2; } L[10500]; 25 int eh[10005],vis[10005]; 26 int i,j,n,m,k,cnt,num,tot; 27 double d[10050],x,y; 28 29 double cj(node a,node b) { return a.x * b.y - a.y * b.x; } 30 31 bool check(Line L1,Line L2) // L1 is a Line and L2 is a segment 32 { 33 node s1( L2.p1.x-L1.p1.x,L2.p1.y-L1.p1.y ); 34 node s2( L2.p2.x-L1.p1.x,L2.p2.y-L1.p1.y ); 35 36 node Ex( L1.p2.x-L1.p1.x,L1.p2.y-L1.p1.y ); 37 38 if ( cj(s1,Ex) * cj(s2,Ex) >= 0 ) return 0; 39 return 1; 40 } 41 42 bool work(node A,node B) 43 { 44 Line t; 45 t.p1 = A; t.p2 = B; 46 for (int k = 1; k <= num; k++) 47 if ( check(t,L[k]) && check(L[k],t) ) return 0; 48 return 1; 49 } 50 51 void add(int a,int b) 52 { 53 double dit = (P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y); 54 dit = sqrt(dit); 55 56 h[cnt] = nd( b,dit,eh[a] ); eh[a] = cnt++; 57 h[cnt] = nd( a,dit,eh[b] ); eh[b] = cnt++; 58 } 59 60 void spfa() 61 { 62 for (int i = 0; i <= tot; i++) d[i] = inf; 63 d[0] = 0; Q.push(0); 64 while (!Q.empty()) 65 { 66 int now = Q.front(); Q.pop(); vis[now] = 0; 67 for (int i = eh[now]; i + 1; i = h[i].next) 68 { 69 int y = h[i].y; 70 if (d[y] > d[now] + h[i].c) 71 { 72 d[y] = d[now]+h[i].c; 73 if (!vis[y]) vis[y] = 1,Q.push(y); 74 } 75 } 76 } 77 } 78 79 int main() 80 { 81 while ( scanf("%d",&n),n != -1 ) 82 { 83 memset(eh,-1,sizeof(eh)); cnt = num = tot = 0; 84 for (i = 1; i <= n; i++) 85 { 86 scanf("%lf",&x); 87 for (j = 1; j <= 4; j++) 88 { 89 scanf("%lf",&y); 90 P[++tot] = node(x,y); 91 } 92 L[++num].p1 = node(x,0); L[num].p2 = P[tot-3]; 93 L[++num].p1 = P[tot-2]; L[num].p2 = P[tot-1]; 94 L[++num].p1 = P[tot]; L[num].p2 = node(x,10); 95 } 96 97 P[0] = node(0,5); P[++tot] = node(10,5); 98 99 for (i = 0; i <= tot; i++)100 for (j = i+1; j <= tot; j++)101 if ( work(P[i],P[j]) ) add(i,j);102 103 spfa();104 printf("%.2lf\n",d[tot]);105 }106 107 return 0;108 }
枚举所有点对，判断是否可行，若可行则连边。然后跑一个SPFA算最短路就行了。
【POJ2007】题意：给一个凸包，要求极角排序后输出。
极角排序：以原点为基准，按逆时针将点排序。
方法：用叉积判断方向，可以确定两个向量的相对位置，就可以用来写cmp函数了。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <cmath> 6 using namespace std; 7 8 struct node 9 {10 int x,y;11 node (){}12 node (int a,int b) : x(a),y(b) {}13 } P[105];14 int i,j,n,m,k,top,x,y;15 16 int cj(node a,node b) { return a.x*b.y-a.y*b.x; }17 bool cmp(node a,node b) { return cj(a,b) > 0; }18 node operator-(node a,node b) { return node(a.x-b.x,a.y-b.y); }19 20 int main()21 {22 while ( scanf("%d %d",&x,&y) != EOF ) { i++; P[i] = node(x,y); }23 24 n = i;25 stable_sort(P+1,P+1+n,cmp);26 for (i = 1; i <= n; i++)27 printf("(%d,%d)\n",P[i].x,P[i].y);28 29 return 0;30 }
【POJ3304】题意：给定n条直线，判断是否有一条直线能让所有直线投影到这条直线上后有公共点。
转换一下题面，其实是要求是否有一条直线与所有直线相交。因为如果有这样的直线，那么这条直线的垂线肯定是符合题面要求的直线。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #define eps 1e-8 7 using namespace std; 8 9 struct node10 {11 double x,y;12 node(){}13 node (double a,double b) { x = a,y = b; }14 }P[205];15 struct Line { node po,ve; } L[105];16 int i,j,n,m,k,num,T;17 18 double cj(node a,node b) { return a.x*b.y-a.y*b.x; }19 void getpoint(node &x)20 {21 double a,b;22 scanf("%lf %lf",&a,&b);23 x = node(a,b);24 }25 26 bool check(Line X,Line Z)27 {28 node s1( Z.po.x-X.po.x,Z.po.y-X.po.y );29 node s2( Z.ve.x-X.po.x,Z.ve.y-X.po.y );30 31 if ( cj(s1,X.ve) * cj(s2,X.ve) <= 0 ) return 1;32 return 0;33 }34 35 bool work()36 {37 for (i = 1; i <= num; i++)38 for (j = i+1; j <= num; j++)39 {40 node a = P[i], b = P[j];41 42 if ( fabs(a.x-b.x) < eps && fabs(a.y-b.y) < eps ) continue;43 44 Line S;45 S.po = a; S.ve = node( b.x-a.x,b.y-a.y );46 47 int find = 1;48 for (k = 1; k <= n; k++)49 if ( !check(S,L[k]) ) { find = 0; break; }50 if (!find) continue;51 52 return 1;53 }54 return 0;55 }56 57 int main()58 {59 scanf("%d",&T);60 while (T--)61 {62 scanf("%d",&n); num = 0;63 for (i = 1; i <= n; i++)64 {65 node a,b;66 getpoint(a); getpoint(b);67 L[i].po = a; L[i].ve = b;68 P[++num] = a; P[++num] = b;69 }70 71 if ( work() ) printf("Yes!\n"); else printf("No!\n");72 }73 74 return 0;75 }
暂时先这么多。
【计算几何】基础总结+题目推荐
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。