首页 > 代码库 > poj 3525 Most Distant Point from the Sea 半平面交 + 二分
poj 3525 Most Distant Point from the Sea 半平面交 + 二分
题目来源:
http://poj.org/problem?id=3525
分析:
题意:给定一个凸多边形,求多边形中距离边界最远的点到边界的距离。
思路 : 每次将凸多边形每条边往里平移d,判断是否存在核;二分d即可。
多边形边上的点(x , y)往里平移d 后的 坐标: s , e 为向量的 起点和终点, len 为起点和终点的距离, h 为平移的距离
x‘ = x + dx
y‘ = y + dy
dx = ( s.y - e.y ) / len * h ,( 原理 是 利用 三角形的相似比 )
dy = ( e.x - s.x ) / len * h ;
代码如下:
const double EPS = 1e-10; const int Max_N = 105 ; struct Point{ double x,y; Point(){} Point(double x, double y):x(x),y(y){} Point operator - (Point p){ return Point(x- p.x , y - p.y ) ; } Point operator + (Point p){ return Point(x+ p.x , y + p.y ) ; } double operator ^ ( Point p){ return x*p.y - y * p.x; } double operator * (Point p){ //内积 点乘 return x*p.x + y * p.y ; } Point operator * (double d){ return Point( x*d, y*d ) ; } bool operator == (Point p){ return fabs(x - p.x ) < EPS && fabs( y - p.y )< EPS ; } double dist(Point p){ return sqrt( (x - p.x)*(x - p.x) + (y - p.y )*(y - p.y) ) ; } }p[Max_N]; struct pVector{ Point s,e; // s 起点, e终点 double a,b,c; // 一般式 ax + by + c = 0 pVector(){} pVector(Point s, Point e):s(s),e(e){} void output(){ cout<<s.x <<" "<<s.y << ":" <<e.x <<" "<< e.y <<endl; } bool operator^( Point p ){ return ( p - s) ^ (e- s); } bool onRight(Point p){ // 点在直线向量的右边 return ( (p - s)^( e - s) )> EPS ; } double operator ^ (pVector _off){ return ((e - s )^( _off.e - _off.s )) ; } bool pton(){ a = s.y - e.y ; b = e.x - s.x ; c = s.x * e.y - s.y * e.x ; return true; } bool parallel(pVector _off){ return fabs( (e - s)^( _off.e - _off.s ) ) < EPS ; } Point crossLPt(pVector _off){ double d1 = ( (_off.e - _off.s)^( _off.s - s ) ) ; double d2 = ( ( _off.e - _off.s )^( e - s ) ) ; return s + ( e - s )*( d1 / d2 ) ; } double jijiao(){ return atan2(e.y - s.y , e.x - s.x) ; } }List[Max_N] , tmp[Max_N]; bool hpc_cmp(pVector l , pVector r){ double lp = l.jijiao() , rp = r.jijiao() ; if( fabs(lp - rp) > EPS ) return lp < rp ; return ( (l.s - r.s)^(r.e - r.s) ) < -EPS ; } //用于 计算的 双端队列 pVector dequeue[Max_N]; Point pt[Max_N] ; // 返回半平面交的 交点 int n; int halfPanelCross(pVector _off[] , int ln){ int i, tn ; sort( _off , _off + ln , hpc_cmp ) ; // 平面在向量左边 的筛选 for( i = tn = 1 ; i < ln ; i++ ){ // 处理极角相同的,选择向量方向最左边的 if( fabs( _off[i].jijiao() - _off[i-1].jijiao() ) > EPS ) //除去极角相同的向量 _off[tn ++] = _off[i] ; } ln = tn ; // 预处理后长度 int bot = 0, top = 1 ; // 队列的两个指针首尾 dequeue[0] = _off[0] ; dequeue[1] = _off[1] ; Point topcross, botcross ; for(i = 2 ; i < ln ; i++){ // 枚举有向直线 if( dequeue[top].parallel( dequeue[top - 1] ) || dequeue[bot].parallel( dequeue[bot + 1] ) ) // 剪枝 : 如果f方向相反的2个向量平行 则 为空集 return 0; while( bot < top && _off[i].onRight( topcross = dequeue[top].crossLPt(dequeue[top - 1]) ) ) // 交点在向量的右边,删除头无用边 top-- ; while( bot< top && _off[i].onRight( botcross = dequeue[bot].crossLPt(dequeue[bot + 1]) ) ) //交点在向量的右边,删除尾无用边 bot ++ bot ++ ; dequeue[ ++ top] = _off[i] ; // 将当前直线加入队列 } // 处理链接处 若队首交点在队尾直线的右边, 队首出列 , 若队尾的交点在队首直线的右边, 队尾出列 while( bot < top && dequeue[bot].onRight( topcross = dequeue[top].crossLPt(dequeue[top - 1]) )) top -- ; while(bot < top && dequeue[top].onRight( botcross = dequeue[bot].crossLPt(dequeue[bot + 1]) )) bot ++ ; if( top <= bot + 1) return 0; // 若队列为空, 则空集 else return 1; } // 多边形每条有向直线向内平移 h 距离 后的有向直线 利用的是三角形的相似 void polygonschange(double h , int ln ){ double len , dx, dy; for(int i=0 ; i< ln ; i++){ len =List[i].s.dist(List[i].e) ; dx = (List[i].s.y - List[i].e.y) / len * h ; dy = (List[i].e.x - List[i].s.x) / len * h ; tmp[i].s.x = List[i].s.x + dx ; tmp[i].s.y = List[i].s.y + dy ; tmp[i].e.x = List[i].e.x + dx ; tmp[i].e.y = List[i].e.y + dy ; } } double BinSearch(int ln){ double l = 0 , r = 20000 , mid; while( l + EPS < r ){ mid = (l + r) * 0.5 ; polygonschange(mid, ln ); if(halfPanelCross(tmp , ln)) l = mid; else r = mid; } return l; } int main(){ int t, i , j , k =1 , ln; while(scanf("%d",&ln) && ln){ for(i = 0 ; i< ln ; i++) scanf("%lf%lf", &p[i].x , &p[i].y) ; for(i = 0; i<ln ; i++){ List[i] = pVector( p[i] , p[(i+1) % ln ] ) ; //构造有向直线(半平面在向量的左边) } double dis = BinSearch(ln) ; printf("%.6lf\n" , dis) ; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。