Lflame

半平面交 !!!

    之前信心满满地以为自己会了...然而今天考试依旧思考了很久...

    注意需要处理的 :加大方框,排序并且手动去重。


    步骤 :

    首先加入大方框,再按极角排序,若极角相同,那么去掉靠外的半平面。

    然后开始做,维护一个队列,每次对于一个半平面L[i],加入前判断队尾两个半平面是否平行(平行则说明退化或交集为空,直接return false),判队尾是否弹出,再判队首是否弹出,最后将L[i]加入队尾。

    加入完成后,再用队首删队尾,队尾删队首。注意 ! 这里若队列中的半平面少于三个,说明无解。

    UPD : 朴心哥今天过来和我讨论了一番...不过最后结论还是这样做确实是正确的...然后发现貌似 lk 也没有特别懂...为了避免蒟蒻的自己忘掉,还是再补上一点点。

    当出现了如下的情况时(为了简化,没有画方框,并且注意此处极角的定义与atan2求得的不同),默认直线左边表示半平面,其中蓝色区域为之前半平面交集,现在箭头向着右下方的半平面加入,可以看出,加入后交集应该为空。那么程序会不会正确判断呢 ? 显然是会的,首先会弹掉队尾的半平面,直到队中只剩下一个半平面,最后再将其加入队列。然后因为是按极角排的序,那么以后再加入半平面时,极角一定是大于最后加入的这个半平面的。可以发现,无论怎么加入,在队首删队尾,队尾删队首后,都只会剩下不超过两个半平面。于是程序判断正确。


    判半平面交是否退化(或为空)的主过程 :

bool get_it()

{

head=tail=0 ;

for(int i=1;i<=Lnum;++i){

if(tail-head>1 && (is_pal(que[tail-1],que[tail-2])||is_pal(que[head],que[head+1])))return false ;

while(tail-head>1 && is_out(L[i],intersect(que[tail-1],que[tail-2])))tail -- ;

while(tail-head>1 && is_out(L[i],intersect(que[head],que[head+1])))head ++ ;

que[tail++]=L[i] ;

}

while(tail-head>2 && is_out(que[head],intersect(que[tail-1],que[tail-2])))tail -- ;

while(tail-head>2 && is_out(que[tail-1],intersect(que[head],que[head+1])))head ++ ;

if(tail-head<3)return false ;

return true ;

}

    

    添加一句,若返回的 true,那么最后队列里面的半平面所围起来的区域即为所求的交。

评论(6)