UVA LA2797 二分加半平面交，很巧妙的二分-白红宇的个人博客

UVA LA2797 二分加半平面交，很巧妙的二分

发布日期：2021-10-08 15:48:54 浏览次数：14 分类：技术文章

本文共 1248 字，大约阅读时间需要 4 分钟。

二分真是个神奇的东西，又是一个二分题目，而且这题分析的半平面交也比较巧妙，本人智商不够，二分和半平面交均想不到，

并且这题二分为什么会对，本渣渣也不太明白，留着慢慢的明白吧。

分析：

如果敌人只有一颗炸弹，你会把总部建在哪里呢？对于每个点，炸掉它以后不会暴露在外面的区域是一条有向直线的”左边“。这让我们想到了什么？

没错，半平面交！综合考虑所有点，所以建总部的范围就是所有这些半平面的交。

如果敌人有俩颗炸弹，总部应该建在哪里呢？分析后发现，敌人最聪明的做法是炸掉俩个连续的顶点，而不是分散火力（想一想，为什么）。这样，

每两个连续顶点对应一个新的半平面，可以建总部的范围仍然是所有半平面的交。

有了上面的分析，整个问题迎刃而解：二分答案，用上述方法判断大难是否可行（也就是半平面交是否为非空）。二分需要O（logn)时间，半平面交需要

O（nlogn）时间，总时间复杂度为O（n^2logn).

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;const double eps=1e-16;const int maxn=50000+10;int dcmp(double x){ if(fabs(x)
               
                0?1:-1; //return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);}struct point{ double x; double y; point(){} point(double x,double y):x(x),y(y){} void in() { cin>>x>>y; } void out() { cout<
                
                 <<' '<
                 
                  <
                  
                   0;}point getintersection(line a,line b){ point u=a.p-b.p; double t=cross(b.v,u)/cross(a.v,b.v); return a.p+a.v*t;}point p[maxn];line q[maxn];point poly[maxn],pt[maxn];line l[maxn];int halfplaneintersection(line *l,int n,point *poly){ sort(l,l+n); int first,last; // point *p=new point[n]; // line *q=new line[n]; q[first=last=0]=l[0]; for(int i=1;i
                   
                    >1; for(int i=0;i
                    
                     >n) { for(int i=0;i

转载地址：https://blog.csdn.net/ONE_PIECE_HMH/article/details/45627323 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：计算几何中的精度问题转载自hust Erbao

下一篇：UVA LA 2218 列出不等式整理成半平面的形式来求半平面交，注意特判

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章