首页 > 代码库 > 【旋转卡壳】poj3608 Bridge Across Islands
【旋转卡壳】poj3608 Bridge Across Islands
给你俩凸包,问你它们的最短距离。
咋做就不讲了,经典题,网上一片题解。
把凸包上的点逆时针排序。可以取它们的平均点,然后作极角排序。
旋转卡壳其实是个很模板化的东西……
先初始化分别在凸包P和Q上取哪个点,一般在P上取纵坐标最小的点,在Q上取纵坐标最大的点
for i=1 to n(n是凸包P上的点数)
{
while(两条边的叉积>0)
{
凸包Q上的点++
}
计算当前两条边之间的答案(或者说每条边的2个端点到另一条边的答案)
凸包P上的点++
}
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define EPS 0.0000000001 struct Point { double x,y; Point(){} Point(const double &X,const double &Y) { x=X; y=Y; } double Length() { return sqrt(x*x+y*y); } }p[2][10010],bao[2][10010],ave; typedef Point Vector; Vector operator - (const Point &a,const Point &b) { return Vector(a.x-b.x,a.y-b.y); } bool cmp (const Point &a,const Point &b) { return atan2((a-ave).y,(a-ave).x)<atan2((b-ave).y,(b-ave).x); } double Cross(const Vector &a,const Vector &b) { return a.x*b.y-a.y*b.x; } double Dot(const Vector &a,const Vector &b) { return a.x*b.x+a.y*b.y; } double calc(Point P,Point A,Point B) { Vector v1=B-A,v2=P-A,v3=P-B; if(Dot(v1,v2)<EPS) return v2.Length(); else if(Dot(v1,v3)>(-EPS)) return v3.Length(); else return fabs(Cross(v1,v2))/v1.Length(); } int n,m; int main() { //freopen("y.in","r",stdin); while(1) { scanf("%d%d",&n,&m); if(n==0 && m==0) break; for(int i=0;i<n;++i) { scanf("%lf%lf",&p[0][i].x,&p[0][i].y); ave.x+=p[0][i].x; ave.y+=p[0][i].y; } ave.x/=(double)n; ave.y/=(double)n; for(int i=0;i<m;++i) scanf("%lf%lf",&p[1][i].x,&p[1][i].y); sort(p[0],p[0]+n,cmp); ave.x=ave.y=0; for(int i=0;i<m;++i) { ave.x+=p[1][i].x; ave.y+=p[1][i].y; } ave.x/=(double)m; ave.y/=(double)m; sort(p[1],p[1]+m,cmp); int nowP=0,nowQ=0; for(int i=1;i<n;++i) if(p[0][i].y-p[0][nowP].y<(-EPS)) nowP=i; for(int i=1;i<m;++i) if(p[1][i].y-p[1][nowQ].y>EPS) nowQ=i; double ans=1000000000000000007.0; for(int i=0;i<n;++i) { while(Cross(p[1][(nowQ+1)%m]-p[1][nowQ],p[0][nowP]-p[0][(nowP+1)%n])>EPS) nowQ=(nowQ+1)%m; ans=min(ans, min(calc(p[0][nowP],p[1][nowQ],p[1][(nowQ+1)%m]), min(calc(p[0][(nowP+1)%n],p[1][nowQ],p[1][(nowQ+1)%m]), min(calc(p[1][nowQ],p[0][nowP],p[0][(nowP+1)%n]), calc(p[1][(nowQ+1)%m],p[0][nowP],p[0][(nowP+1)%n]))))); nowP=(nowP+1)%n; } printf("%.5lf\n",ans); } return 0; }
【旋转卡壳】poj3608 Bridge Across Islands
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。