首页 > 代码库 > poj 3384 Feng Shui 半平面交的应用 求最多覆盖凸多边形的面积的两个圆 的圆心坐标
poj 3384 Feng Shui 半平面交的应用 求最多覆盖凸多边形的面积的两个圆 的圆心坐标
题目来源:
http://poj.org/problem?id=3384
分析: 用半平面交将多边形的每条边一起向“内”推进R,得到新的多边形(半平面交),然后求多边形的最远两点。
代码如下:
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] , tmpp[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 halfPanelCross(pVector _off[] , int ln){ int i, tn ,n; 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; // 若队列为空, 则空集 n = 0; for( i = bot ; i <top ; i++) pt[n ++] = dequeue[i].crossLPt(dequeue[i+1] ) ; if(bot <top + 1) pt[n ++] = dequeue[bot].crossLPt(dequeue[top]) ; return n; } // 多边形每条有向直线向内平移 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 ; } } int main(){ int t, i , j , ln ; double rad; while(scanf("%d%lf",&ln , &rad) != EOF){ 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+1) % ln ] , p[i]) ; //构造有向直线(半平面在向量的左边) } polygonschange(rad, ln) ; int n = halfPanelCross(tmp, ln) ; // 多边形平移后求半平面交凸多边形的 顶点 double Max = 0.0 ; int k1 = 0,k2 = 0 ; for(i = 0 ; i< n; i++){ //寻找凸多边形中最远点对 , 枚举 for(j = i+1 ; j < n ; j++){ if (pt[i].dist(pt[j]) > Max){ Max = pt[i].dist(pt[j]) ; k1 = i; k2 = j; } } } printf("%.4lf %.4lf %.4lf %.4lf\n" , pt[k1].x , pt[k1].y , pt[k2].x , pt[k2].y) ; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。