Bridge Across Islands
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7202   Accepted: 2113   Special Judge

Description

Thousands of thousands years ago there was a small kingdom located in the middle of the Pacific Ocean. The territory of the kingdom consists two separated islands. Due to the impact of the ocean current, the shapes of both the islands became convex polygons. The king of the kingdom wanted to establish a bridge to connect the two islands. To minimize the cost, the king asked you, the bishop, to find the minimal distance between the boundaries of the two islands.

Input

The input consists of several test cases.
Each test case begins with two integers NM. (3 ≤ NM ≤ 10000)
Each of the next N lines contains a pair of coordinates, which describes the position of a vertex in one convex polygon.
Each of the next M lines contains a pair of coordinates, which describes the position of a vertex in the other convex polygon.
A line with N = M = 0 indicates the end of input.
The coordinates are within the range [-10000, 10000].

Output

For each test case output the minimal distance. An error within 0.001 is acceptable.

Sample Input

4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0

Sample Output

1.00000

Source

 
 
 
 
 
经典算法。
 
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std; const double eps = 1e-;
int sgn(double x)
{
if(fabs(x) < eps)return ;
if(x < )return -;
else return ;
}
struct Point
{
double x,y;
Point(double _x = 0.0,double _y = 0.0)
{
x = _x;
y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x, y - b.y);
}
double operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
double operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
void input()
{
scanf("%lf%lf",&x,&y);
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point _s,Point _e)
{
s = _s;
e = _e;
}
};
double dist(Point a,Point b)
{
return sqrt((a-b)*(a-b));
}
Point NearestPointToLineSeg(Point P,Line L)
{
Point result;
double t = ((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));
if(t >= && t <= )
{
result.x = L.s.x + (L.e.x - L.s.x)*t;
result.y = L.s.y + (L.e.y - L.s.y)*t;
}
else
{
if(dist(P,L.s) < dist(P,L.e))
result = L.s;
else result = L.e;
}
return result;
}
/*
* 求凸包,Graham算法
* 点的编号0~n-1
* 返回凸包结果Stack[0~top-1]为凸包的编号
*/
const int MAXN = ;
Point list[MAXN];
int Stack[MAXN],top;
//相对于list[0]的极角排序
bool _cmp(Point p1,Point p2)
{
double tmp = (p1-list[])^(p2-list[]);
if(sgn(tmp) > )return true;
else if(sgn(tmp) == && sgn(dist(p1,list[]) - dist(p2,list[])) <= )
return true;
else return false;
}
void Graham(int n)
{
Point p0;
int k = ;
p0 = list[];
//找最下边的一个点
for(int i = ;i < n;i++)
{
if( (p0.y > list[i].y) || (p0.y == list[i].y && p0.x > list[i].x) )
{
p0 = list[i];
k = i;
}
}
swap(list[k],list[]);
sort(list+,list+n,_cmp);
if(n == )
{
top = ;
Stack[] = ;
return;
}
if(n == )
{
top = ;
Stack[] = ;
Stack[] = ;
return ;
}
Stack[] = ;
Stack[] = ;
top = ;
for(int i = ;i < n;i++)
{
while(top > && sgn((list[Stack[top-]]-list[Stack[top-]])^(list[i]-list[Stack[top-]])) <= )
top--;
Stack[top++] = i;
}
}
//点p0到线段p1p2的距离
double pointtoseg(Point p0,Point p1,Point p2)
{
return dist(p0,NearestPointToLineSeg(p0,Line(p1,p2)));
}
//平行线段p0p1和p2p3的距离
double dispallseg(Point p0,Point p1,Point p2,Point p3)
{
double ans1 = min(pointtoseg(p0,p2,p3),pointtoseg(p1,p2,p3));
double ans2 = min(pointtoseg(p2,p0,p1),pointtoseg(p3,p0,p1));
return min(ans1,ans2);
}
//得到向量a1a2和b1b2的位置关系
double Get_angle(Point a1,Point a2,Point b1,Point b2)
{
Point t = b1 - ( b2 - a1 );
return (a2-a1)^(t-a1);
}
//旋转卡壳,求两个凸包的最小距离
double rotating_calipers(Point p[],int np,Point q[],int nq)
{
int sp = , sq = ;
for(int i = ;i < np;i++)
if(sgn(p[i].y - p[sp].y) < )
sp = i;
for(int i = ;i < nq;i++)
if(sgn(q[i].y - q[sq].y) > )
sq = i;
double tmp;
double ans = 1e99;
for(int i = ;i < np;i++)
{
while(sgn(tmp = Get_angle(p[sp],p[(sp+)%np],q[sq],q[(sq+)%nq])) < )
sq = (sq + )%nq;
if(sgn(tmp) == )
ans = min(ans,dispallseg(p[sp],p[(sp+)%np],q[sq],q[(sq+)%nq]));
else ans = min(ans,pointtoseg(q[sq],p[sp],p[(sp+)%np]));
sp = (sp+)%np;
}
return ans;
} double solve(Point p[],int n,Point q[],int m)
{
return min(rotating_calipers(p,n,q,m),rotating_calipers(q,m,p,n));
}
Point p[MAXN],q[MAXN];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==)
{
if(n == && m == )break;
for(int i = ;i < n;i++)
list[i].input();
Graham(n);
n = top;
for(int i = ;i < n;i++)
p[i] = list[Stack[i]];
for(int i = ;i < m;i++)
list[i].input();
Graham(m);
m = top;
for(int i = ;i < m;i++)
q[i] = list[Stack[i]];
printf("%.5lf\n",solve(p,n,q,m));
}
return ;
}
 
 
 
 
 

最新文章

  1. MySQL连表操作之一对多
  2. Win 2003硬盘安全设置
  3. CSS选择器的特殊性
  4. datatable 行列转换
  5. ArcEngine下一个TIN生成的轮廓
  6. 使用SQL存储过程有什么好处 用视图有什么好处
  7. Tensorflow--矩阵切片与连接
  8. Nginx整合tomcat,实现反向代理和负载均衡
  9. python requests + xpath 获取分页详情页数据存入到txt文件中
  10. Idea spring 配置文件报红 URI is not registered
  11. gif软件(ShareX)
  12. HIbernate处理数据更新丢失
  13. 堆排序(Heapsort)
  14. 《ASP.NET MVC企业实战》(一) MVC开发前奏
  15. Keil5 如何安装STM32 芯片包
  16. MYSQL + MHA +keepalive + VIP安装配置(一)--MYSQL安装配置
  17. [Unity3D]Unity3D游戏开发之跑酷游戏项目解说
  18. iOS 10.3.3 更新背后的故事
  19. 根据wsdl,基于wsimport生成代码的客户端
  20. BZOJ3230: 相似子串【后缀数组】

热门文章

  1. TCP之Nagle算法&amp;&amp;延迟ACK
  2. 使用 ftrace 调试 Linux 内核【转】
  3. debian下没有公钥解决办法
  4. django使用haystack对接Elasticsearch实现商品搜索
  5. POJ 1984 Navigation Nightmare(二维带权并查集)
  6. HDU-5384
  7. Linux安装mysql.8.0.12
  8. java和js生成二维码
  9. 在C#中使用正则表达式筛选出图片URL并下载图片URL中的图片到本地
  10. python模块安装路径