UVALive 4992 Jungle Outpost（半平面交）-白红宇

UVALive 4992 Jungle Outpost（半平面交）

阅读量：5829 次

发布时间：2019-06-18

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

题意：给你n个塔（点）形成一个顺时针的凸包，敌人可以摧毁任何塔，摧毁后剩下的塔再组成凸包

　　　在开始的凸包内选一点为主塔，保证敌人摧毁尽量多塔时主塔都还在现在的凸包内，求出最多摧毁的塔

题解：这题关键就是选的主塔在不同的地方，敌人就会摧毁不同的塔来让你的主塔暴露

因此这样想，找出敌人摧毁不同的塔后形成的所有不同的凸包，再求出所有凸包的交就好

具体就是，首先枚举摧毁塔的个数k，再把摧毁任意k个塔所形成的所有不同的凸包求一个交，如果为空就代表了摧毁k个塔一定可以保证无论主塔在哪儿都可以暴露（关键）

而所有凸包的交可以将其转化为找到所有凸包上的直线求半平面交，接着就是注意敌人摧毁连续的k个塔一定是最优的，所以求半平面交的直线只要n条（理解一下）

最后可以发现答案满足单调性，可以二分答案

再然后这儿有个小trick就是找直线时需要逆时针找（因为半平面交是逆时针来求的）

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define sgn(x) (x<-eps? -1 :x
                  
                    0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                   
                    >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const ll INF=1ll<<60;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=50010;struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y) {}; int read() { scanf("%lf%lf",&x,&y); } inline Point operator+(const Point& a)const { return Point(x+a.x,y+a.y); } inline Point operator*(double a)const { return Point(x*a,y*a); } inline Point operator-(const Point& a)const { return Point(x-a.x,y-a.y); } inline bool operator<(const Point& a)const { return sgn(x-a.x)<0||zero(x-a.x)&&sgn(y-a.y)<0; } inline bool operator!=(const Point& a)const { return !(zero(x-a.x)&&zero(y-a.y)); }};typedef Point Vector;struct Line{ Point p; Vector v; double ang;//极角 Line() {}; Line(Point p,Vector v):p(p),v(v) { ang=atan2(v.y,v.x); } inline bool operator<(const Line& L)const { return ang
                    
                     0;}Point GetIntersection(Line a,Line b){ Vector u=a.p-b.p; double t=Cross(b.v,u)/Cross(a.v,b.v); return a.p+a.v*t;}int HarfplaneIntersection(Line *L,int n){ sort(L,L+n);// for(int i=0; i
                     
                      >1);//代表删多少个点 if(Solve(mid,n))//非空即为需要删除更多的点 { lef=mid+1; } else { rig=mid; } } return lef;}int main(){ int n; while(~scanf("%d",&n)) { for(int i=0; i

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/6286451.html

你可能感兴趣的文章