POJ 3608 Bridge Across Islands（旋转卡壳求凸多边形最短距离）

POJ 3608 Bridge Across Islands（旋转卡壳求凸多边形最短距离）

​​点和线段e的距离最短

(2) 点和新点的距离最短（旧点之前已经判断了）

当两条平行线均和凸多边形的边重合时：

(3) 线段和线段的距离是最短的（一段距离）

(4) 最短距离产生于线段的端点的距离（四段距离）

上面的求解情况转化成 点到点的距离，点到线的距离，线到线的距离（可转化成点到线的距离）

#include #include #include #include using namespace std;const double eps=1e-7,inf=1e99;const int N=1e4+10;struct point{ double x,y;};double dis(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double cross(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}double multi(point p0,point p1,point p2){ //点积 p0为角点 return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);}double getDis(point p0,point p1,point p2){ if(dis(p0,p1)q[ymax].y) ymax=i; } p[top1]=p[0]; q[top2]=q[0]; double t,ans=inf; for(int i=0;ieps) ans=min(ans,getDis(p[ymin],p[ymin+1],q[ymax])); else ans=min(ans,minDis(p[ymin],p[ymin+1],q[ymax],q[ymax+1])); ymin=(ymin+1)%top1; } return ans;}point p[N],q[N];int top1,top2;int main(){ //freopen("cin.txt","r",stdin); while(cin>>top1>>top2&&(top1+top2)){ for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。