网站推广策划报告,图片瀑布流网站模板,网络营销策略和营销策略的区别,做网站的经历感想1.计算P上y坐标值最小的顶点#xff08;称为 yminP #xff09;和Q上y坐标值最大的顶点#xff08;称为 ymaxQ#xff09;。 2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。 此时 LP 和 LQ 拥有不同的方向#xff0c; 并且 y…1.计算P上y坐标值最小的顶点称为 yminP 和Q上y坐标值最大的顶点称为 ymaxQ。 2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。 此时 LP 和 LQ 拥有不同的方向 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。 3.计算距离(yminP,ymaxQ) 并且将其维护为当前最小值。 4.顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。 5.如果只有一条线与边重合 那么只需要计算“顶点-边”对踵点对和“顶点-顶点”对踵点对距离。 都将他们与当前最小值 比较 如果小于当前最小值则进行替换更新。如果两条切线都与边重合那么情况就更加复杂了。如果边“交叠”也就是 可以构造一条与两条边都相交的公垂线但不是在顶点处相交 那么就计算“边-边”距离。 否则计算三个新的“顶点-顶 点”对踵点对距离。 所有的这些距离都与当前最小值进行比较 若小于当前最小值则更新替换。 6.重复执行步骤4和步骤5 直到新的点对为(yminP,ymaxQ)。 7.输出最小距离 这是求两凸包最短距离的经典算法。但是不知为什么我的代码死活过不了。。。T_T 1 #include iostream2 #include cstdio3 #include cstring4 #include algorithm5 #include cmath6 using namespace std;7 const double eps0.00000001;8 9 struct point {10 double x,y;11 }p[10050],q[10050];12 int n,m;13 int ansp[10050],ansq[10050],cntp,cntq;14 int st[10050],stop;15 16 bool cmp(point A,point B){17 if(A.yB.y) return true;18 else if(A.yB.y){19 if(A.xB.x) return true;20 }21 return false;22 }23 24 double dist(point a , point b){25 return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));26 }27 28 double multi(point a, point b, point c){29 point p1; p1.xa.x-c.x; p1.ya.y-c.y;30 point p2; p2.xb.x-c.x; p2.yb.y-c.y;31 return (p1.x*p2.y-p1.y*p2.x);32 }33 34 void forTU(point *pot, int allVex, int *anp, int cnt){35 // coutallVexallendl;36 stopcnt0;37 st[stop]0; st[stop]1;38 for(int i2;iallVex;i){39 while(stop1multi(pot[i],pot[st[stop-1]],pot[st[stop-2]])0) stop--;40 st[stop]i;41 }42 for(int i0;istop;i)43 anp[cnt]st[i];44 stop0;45 st[stop]allVex-1; st[stop]allVex-2;46 for(int iallVex-3;i0;i--){47 while(stop1multi(pot[i],pot[st[stop-1]],pot[st[stop-2]])0) stop--;48 st[stop]i;49 }50 for(int i1;istop;i)51 anp[cnt]st[i];52 // for(int i0;icnt;i)53 // coutanp[i]endl;54 // coutendl;55 }56 57 double dotcross(point a,point b, point c){58 point p1; p1.xa.x-c.x; p1.ya.y-c.y;59 point p2; p2.xb.x-c.x; p2.yb.y-c.y;60 return p1.x*p2.xp1.y*p2.y;61 }62 63 double pline(point a,point b,point c){64 return (fabs(multi(a,b,c)))/(dist(a,b));65 }66 67 double pseg(point a,point b,point c){68 if(dotcross(a,c,b)-eps) return dist(b,c);69 if(dotcross(b,c,a)-eps) return dist(a,c);70 return pline(a,b,c);71 }72 73 double paral(point a1,point a2, point b1,point b2 ){74 double ans1min(pseg(a1,a2,b1),pseg(a1,a2,b2));75 double ans2min(pseg(b1,b2,a1),pseg(b1,b2,a2));76 return min(ans1,ans2);77 }78 79 int sgn(double x)80 {81 if(fabs(x) eps)return 0;82 if(x 0)return -1;83 else return 1;84 }85 86 double Get_angle(point a1,point a2,point b1,point b2)87 {88 point p1; p1.xa1.x-a2.x; p1.ya1.y-a2.y;89 point p2; p2.xb1.x-b2.x; p2.yb1.y-b2.y;90 return p1.x*p2.y-p1.y*p2.x;91 }92 93 double slove(point *p, int *ap, int cp, point *q, int *aq, int cq){94 int sp0,sq0; double tmp;95 for(int i0;icq;i) //max96 if(q[aq[i]].y-epsq[aq[sq]].y) sqi;97 double resdist(p[ap[sp]],q[aq[sq]]);98 for(int i0;icp;i){99 // while((tmpfabs(multi(p[ap[i]],p[ap[i1]],q[aq[sq]])/2)-fabs(multi(p[ap[i]],p[ap[i1]],q[aq[(sq1)%cq]])/2))eps)
100 // while(tmpmulti(p[ap[i]],p[ap[i1]],q[aq[(sq1)%cq]])-multi(p[ap[i]],p[ap[i1]],q[aq[sq]])eps)
101 // sq(sq1)%cq;
102 // if(tmp-eps){
103 while(sgn(tmp Get_angle(p[i],p[(i1)%cp],q[sq],q[(sq1)%cq])) 0 )
104 sq (sq 1)%cq;
105 if(sgn(tmp) 0)
106 resmin(res,pseg(p[ap[i]],p[ap[i1]],q[aq[sq]]));
107 // coutresendl;
108 // }
109 else{
110 resmin(res,paral(p[ap[i]],p[ap[i1]],q[aq[sq]],q[aq[(sq1)%cq]]));
111 // coutresendl;
112 }
113 }
114 return res;
115 }
116
117
118 int main(){
119 double ans10000000;
120 while(scanf(%d%d,n,m)!EOF){
121 if(n0m0) break;
122 for(int i0;in;i)
123 scanf(%lf%lf,p[i].x,p[i].y);
124 for(int i0;im;i)
125 scanf(%lf%lf,q[i].x,q[i].y);
126 sort(p,pn,cmp);
127 sort(q,qm,cmp);
128 forTU(p,n,ansp,cntp);
129 forTU(q,m,ansq,cntq);
130 ans1e99;
131 ansmin(ans,slove(p,ansp,cntp,q,ansq,cntq)); //min,max
132 ansmin(ans,slove(q,ansq,cntq,p,ansp,cntp));
133 printf(%.5lf\n,ans);
134 }
135 return 0;
136 } View Code 别人的代码 #include iostream
#include string.h
#include algorithm
#include stdio.h
#include math.husing namespace std;const int N50000;
const double eps1e-9;
const double INF1e99;struct Point
{double x,y;
};Point P[N],Q[N];double cross(Point A,Point B,Point C)
{return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}double dist(Point A,Point B)
{return sqrt((A.x-B.x)*(A.x-B.x)(A.y-B.y)*(A.y-B.y));
}double multi(Point A,Point B,Point C)
{return (B.x-A.x)*(C.x-A.x)(B.y-A.y)*(C.y-A.y);
}//顺时针排序
void anticlockwise(Point p[],int n)
{for(int i0;in-2;i){double tmpcross(p[i],p[i1],p[i2]);if(tmpeps) return;else if(tmp-eps){reverse(p,pn);return;}}
}//计算C点到直线AB的最短距离
double Getdist(Point A,Point B,Point C)
{if(dist(A,B)eps) return dist(B,C);if(multi(A,B,C)-eps) return dist(A,C);if(multi(B,A,C)-eps) return dist(B,C);return fabs(cross(A,B,C)/dist(A,B));
}//求一条直线的两端点到另外一条直线的距离反过来一样共4种情况
double MinDist(Point A,Point B,Point C,Point D)
{return min(min(Getdist(A,B,C),Getdist(A,B,D)),min(Getdist(C,D,A),Getdist(C,D,B)));
}double Solve(Point P[],Point Q[],int n,int m)
{int yminP0,ymaxQ0;for(int i0;in;i)if(P[i].yP[yminP].y)yminPi;for(int i0;im;i)if(Q[i].yQ[ymaxQ].y)ymaxQi;P[n]P[0];Q[m]Q[0];double tmp,ansINF;for(int i0;in;i){while(tmpcross(P[yminP1],Q[ymaxQ1],P[yminP])-cross(P[yminP1],Q[ymaxQ],P[yminP])eps)ymaxQ(ymaxQ1)%m;if(tmp-eps) ansmin(ans,Getdist(P[yminP],P[yminP1],Q[ymaxQ]));else ansmin(ans,MinDist(P[yminP],P[yminP1],Q[ymaxQ],Q[ymaxQ1]));yminP(yminP1)%n;}return ans;
}int main()
{int n,m;while(cinnm){if(n0m0) break;for(int i0;in;i)cinP[i].xP[i].y;for(int i0;im;i)cinQ[i].xQ[i].y;anticlockwise(P,n);anticlockwise(Q,m);printf(%.5lf\n,min(Solve(P,Q,n,m),Solve(Q,P,m,n)));}return 0;
}转载于:https://www.cnblogs.com/jie-dcai/p/3890912.html
