首页 > 代码库 > 半平面交 模板 poj 3335 poj 3130 poj 1474 判断半平面交是否为空集
半平面交 模板 poj 3335 poj 3130 poj 1474 判断半平面交是否为空集
半平面交模板
const double pi= acos(-1.0); #define arc(x) (x / 180 * pi) const double EPS = 1e-8; 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 ; } }; // 两点表示的向量 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; } // 向量与点的叉乘[ 点相对向量位置判断 ] //返回值> 0 , 则 点在向量的右侧， <0 则 点在向量的左侧 bool operator^( Point p ){ return ( p - s) ^ (e- s); } bool onRight(Point p){ // 点在直线向量的右边 return ( (p - s)^( e - s) )> EPS ; } // 向量与向量(_off)的 叉乘 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 ; } //两直线 交点， 参数 目标直线[_off] 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 hpc_pa(pVector _off){ return atan2( _off.e.y - _off.s.y , _off.e.x - _off.s.x ) ; } // 半平面交 排序函数 [优先顺序：1极角 2. 前面的直线在后面的左边 ] bool hpc_cmp(pVector l , pVector r){ double lp = hpc_pa(l) , rp = hpc_pa(r); 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; //获取 半平面交的 多边形（多边形的核） o(n log(2n)) //参数： 向量集合[l]， 向量数量[ln] （半平面方向在向量的左边） //函数运行后 如果n[即返回多边形的点数量] 为 0 则不存在半平面交的多边形（不存在区域或区域面积无穷大） int halfPanelCross(pVector _off[] , int ln){ int i, tn ; sort( _off , _off + ln , hpc_cmp ) ; // 平面在向量左边 的筛选 for( i = tn = 1 ; i < ln ; i++ ){ // 处理极角相同的，选择向量方向最左边的 if( fabs( hpc_pa( _off[i] ) - hpc_pa( _off[i-1] ) ) > EPS ) //除去极角相同的向量 _off[tn ++] = _off[i] ; } ln = tn ; // 预处理后长度 int bot = 0, top = 1 ; // 队列的两个指针首尾 dequeue[0] = _off[0] ; dequeue[1] = _off[1] ; 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( dequeue[top].crossLPt(dequeue[top - 1]) ) ) // 交点在向量的右边，删除头无用边 top-- top-- ; while( bot< top && _off[i].onRight( dequeue[bot].crossLPt(dequeue[bot + 1]) ) ) //交点在向量的右边，删除尾无用边 bot ++ bot ++ ; dequeue[ ++ top] = _off[i] ; // 将当前直线加入队列 } // 处理链接处 若队首交点在队尾直线的右边， 队首出列 ， 若队尾的交点在队首直线的右边， 队尾出列 while( bot < top && dequeue[bot].onRight( dequeue[top].crossLPt(dequeue[top - 1]) )) top -- ; while(bot < top && dequeue[top].onRight( 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; }
分析： 如果多边形顶点是按照 顺时针给出， 那么向量的构造为：
for(i = 0; i<m ; i++){ List[i] = pVector( p[(i+1) % m ], p[i] ) ; //构造有向直线（半平面在向量的左边） }
如果多变形顶点是按照 逆时针 给出， 那么向量的构造为：
for(i = 0; i<m ; i++){ List[i] = pVector( p[i] , p[(i+1) % m ] ) ; //构造有向直线（半平面在向量的左边） }
题目来源：
http://poj.org/problem?id=3335
判断是否存在半平面交
代码如下：
const double pi= acos(-1.0); #define arc(x) (x / 180 * pi) const double EPS = 1e-8; 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 ; } }; // 两点表示的向量 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; } // 向量与点的叉乘[ 点相对向量位置判断 ] //返回值> 0 , 则 点在向量的右侧， <0 则 点在向量的左侧 bool operator^( Point p ){ return ( p - s) ^ (e- s); } bool onRight(Point p){ // 点在直线向量的右边 return ( (p - s)^( e - s) )> EPS ; } // 向量与向量(_off)的 叉乘 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 ; } //两直线 交点， 参数 目标直线[_off] 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 hpc_pa(pVector _off){ return atan2( _off.e.y - _off.s.y , _off.e.x - _off.s.x ) ; } // 半平面交 排序函数 [优先顺序：1极角 2. 前面的直线在后面的左边 ] bool hpc_cmp(pVector l , pVector r){ double lp = hpc_pa(l) , rp = hpc_pa(r); 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; //获取 半平面交的 多边形（多边形的核） o(n log(2n)) //参数： 向量集合[l]， 向量数量[ln] （半平面方向在向量的左边） //函数运行后 如果n[即返回多边形的点数量] 为 0 则不存在半平面交的多边形（不存在区域或区域面积无穷大） int halfPanelCross(pVector _off[] , int ln){ int i, tn ; sort( _off , _off + ln , hpc_cmp ) ; // 平面在向量左边 的筛选 for( i = tn = 1 ; i < ln ; i++ ){ // 处理极角相同的，选择向量方向最左边的 if( fabs( hpc_pa( _off[i] ) - hpc_pa( _off[i-1] ) ) > EPS ) //除去极角相同的向量 _off[tn ++] = _off[i] ; } ln = tn ; // 预处理后长度 int bot = 0, top = 1 ; // 队列的两个指针首尾 dequeue[0] = _off[0] ; dequeue[1] = _off[1] ; 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( dequeue[top].crossLPt(dequeue[top - 1]) ) ) // 交点在向量的右边，删除头无用边 top-- top-- ; while( bot< top && _off[i].onRight( dequeue[bot].crossLPt(dequeue[bot + 1]) ) ) //交点在向量的右边，删除尾无用边 bot ++ bot ++ ; dequeue[ ++ top] = _off[i] ; // 将当前直线加入队列 } // 处理链接处 若队首交点在队尾直线的右边， 队首出列 ， 若队尾的交点在队首直线的右边， 队尾出列 while( bot < top && dequeue[bot].onRight( dequeue[top].crossLPt(dequeue[top - 1]) )) top -- ; while(bot < top && dequeue[top].onRight( 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; } pVector List[Max_N]; Point p[Max_N]; int main(){ int t, i , j; int m; scanf("%d" , &t); while(t--){ scanf("%d",&m) ; for(i = 0 ; i< m ; i++) scanf("%lf%lf", &p[i].x , &p[i].y) ; for(i = 0; i<m ; i++){ List[i] = pVector( p[(i+1) % m ], p[i] ) ; //构造有向直线（半平面在向量的左边） } if ( halfPanelCross(List, m) ) puts("YES"); else puts("NO") ; } return 0; }
poj 3130 判段半平面交是否为空集， 多边形的顶点是按逆时针输入。 只需更改下 构造有向直线处的代码。
poj 1474 判断 半平面交 是否为空集， 多边形的顶点是按 顺时针输入， 只需更改下 输出代码， 即可。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。