首页 > 代码库 > 旋转卡壳解poj3608Bridge Across Islands
旋转卡壳解poj3608Bridge Across Islands
继续上一次的旋转卡壳的问题,这次是求两个凸包的最短距离,
其实选择卡壳就是只要找到"当前向量面积不小于下一个向量面积"即可,
满足这个条件,当前的两个ymin和ymax点就是一对对踵点了。
代码如下,欢迎参考:
#include<cmath> #include<cstdio> #include<iostream> using namespace std; typedef struct{float x,y;} Dot; Dot operator -(Dot a,Dot b){Dot c={a.x-b.x,a.y-b.y};return c;} float operator *(Dot a,Dot b){return a.x*b.y-b.x*a.y;} float operator /(Dot a,Dot b){return a.x*b.x+a.y*b.y;}//点积判断这个点是否在直线外 float dis(Dot a,Dot b){return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));} float dtl(Dot a,Dot b,Dot c)//c点到线段ab的最短距离 { if((b-a)/(c-a)<0) return dis(c,a); if((a-b)/(c-b)<0) return dis(c,b); return fabs((a-b)*(c-b)/dis(a,b)); } float ltl(Dot a,Dot b,Dot c,Dot d){return min(min(dtl(a,b,c),dtl(a,b,d)),min(dtl(c,d,a),dtl(c,d,b)));} float work(Dot * a,Dot * b,int n,int m) { Dot t; float ans=1e9; int i,ymin=0,ymax=0; for(i=0;i<n;i++) if(a[i].y<a[ymin].y) ymin=i; for(i=0;i<m;i++) if(b[i].y>b[ymax].y) ymax=i; a[n]=a[0];b[m]=b[0]; for(i=0;i<n;i++) { t=a[ymin+1]-a[ymin]; while(t*(b[ymax]-a[ymin])<t*(b[ymax+1]-a[ymin]))//找到当前向量面积不小于下一个向量面积即可 ymax=(ymax+1)%m; ans=min(ans,ltl(a[ymin],a[ymin+1],b[ymax],b[ymax+1])); ymin=(ymin+1)%n; } return ans; } int main() { int i,n,m; Dot a[10010],b[10010]; while(scanf("%d%d",&n,&m)&&n!=0||m!=0) { for(i=0;i<n;i++) scanf("%f%f",&a[i].x,&a[i].y);//单精度跑得快,而且精度是1e-6,对于此题,够用了 for(i=0;i<m;i++) scanf("%f%f",&b[i].x,&b[i].y); printf("%.3f\n",work(a,b,n,m));//精度在1e-3就够了 } }
旋转卡壳解poj3608Bridge Across Islands
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。