题目:计算两个不相交凸多边形间的最小距离。
分析:计算几何、凸包、旋转卡壳。分别求出凸包,利用旋转卡壳求出对踵点对,枚举距离即可。
注意:1.利用向量法判断旋转,而不是计算角度;避免精度问题和TLE。
2.遇到平行线段时,需要计算4组点到线段距离,不然会漏掉对踵点对。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
//点结构
typedef struct pnode
{
double x,y,d;
pnode( double a, double b ) {x = a;y = b;}
pnode(){};
}point;
point T,P[10005],Q[10005];
//线段结构
typedef struct lnode
{
double x,y,dx,dy;
lnode( point a, point b ) {x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}
lnode(){};
}line;
//叉乘 ab*ac
double crossproduct( point a, point b, point c )
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
//两点间距离
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 dist( point a, point p, point q )
{
line l = line( p, q );
//判断垂足位置
if ( (l.dx*(p.x-a.x)+l.dy*(p.y-a.y))*(l.dx*(q.x-a.x)+l.dy*(q.y-a.y)) < 0 )
return fabs(l.dx*(a.y-l.y)-l.dy*(a.x-l.x))/sqrt(l.dx*l.dx+l.dy*l.dy);
else return min( dist( a, p ), dist( a, q ) );
}
//坐标比较
bool cmp1( point a, point b )
{
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
//级角比较
bool cmp2( point a, point b )
{
double cp = crossproduct( T, a, b );
if ( !cp ) return a.d < b.d;
else return cp > 0;
}
//凸包
int graham( point* p, int n )
{
sort( p+0, p+n, cmp1 );
for ( int i = 1 ; i < n ; ++ i )
p[i].d = dist( p[0], p[i] );
T = p[0];
sort( p+1, p+n, cmp2 );
int top = 1;
for ( int i = 2 ; i < n ; ++ i ) {
while ( top > 0 && crossproduct( p[top-1], p[top], p[i] ) <= 0 ) -- top;
p[++ top] = p[i];
}
p[++ top] = p[0];
return top;
}
//利用向量判断夹角
double judge( point a, point b, point c, point d )
{
return crossproduct( c, d, point( c.x+b.x-a.x, c.y+b.y-a.y ) );
}
//旋转卡壳
double rotatingcalipers( point* p, point* q, int n, int m )
{
double D = 30000.0;
int R = 0;
for ( int i = 0 ; i < m ; ++ i )
if ( q[i].x >= q[R].x ) R = i;
for ( int L = 0 ; L < n ; ++ L ) {
while ( judge( p[L], p[L+1], q[R], q[R+1] ) < 1e-6 )
R = (R+1)%m;
//两条边平行时,需计算平行线段间最短距离,即四个点到线段的距离
D = min( min( D, dist( p[L], q[R] ) ),
min( min( dist( p[L], q[R], q[R+1] ), dist( q[R], p[L], p[L+1] ) ),
min( dist( p[L+1], q[R], q[R+1] ), dist( q[R+1], p[L], p[L+1] ) ) ) );
}
return D;
}
int main()
{
int N,M;
while ( scanf("%d%d",&N,&M) && N ) {
for ( int i = 0 ; i < N ; ++ i )
scanf("%lf%lf",&P[i].x,&P[i].y);
for ( int i = 0 ; i < M ; ++ i )
scanf("%lf%lf",&Q[i].x,&Q[i].y);
N = graham( P, N );
M = graham( Q, M );
printf("%.5lf\n",rotatingcalipers( P, Q, N, M ));
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。