Jungle Outpost

思路

首先考虑贪心
先告诉你们一个结论：敌人最少炸坏的瞭望台总是在凸包上是连续的
怎么证明呢，如下图（我可认真了，自己画的）

如图，我们假设破坏了1点和3点，即造成了三角形125和三角形234失去保护
但是我们想如果总部在三角形125中，歹徒何必去让三角形234失去保护呢？
总部在三角形234中同理。
所以可以得出“敌人最少炸坏的瞭望台总是在凸包上是连续的”的结论（证明不太严谨，意会意会）
在考虑如何求解
我们想到二分答案
怎么来判断答案呢？
看下图QWQ

蓝色地区是1号点被破坏时，总部的安全地区
再看一个图！

蓝色地区是3号点被破坏时，总部的安全地区
2，4，5点被破坏同理
当这些蓝色的地方的交集面积大于0时，说明歹徒破坏这么多的塔，总部有地方苟活下去
怎么求交集面积呢？明显的半平面交嘛！！！
思路已经十分明了了
首先二分答案，然后用半平面交判断

优化

当你一顿操作套上了半平面交的板子时。
想要一发入魂，AC此题
然而TLE了！！！
考虑如何优化
题目给定的凸包是有序的，经过我们处理后的边同样是有序的
我们已经不需要对边按照极角排序
就优化掉了一个log

参考代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct point{
    double x,y;
    point(){};
    point(double x,double y):x(x),y(y){};
    point operator-(point b){return point(x-b.x,y-b.y);}
    point operator+(point b){return point(x+b.x,y+b.y);}
    point operator*(double b){return point(x*b,y*b);}
    double operator%(point b){return x*b.y-y*b.x;}
}d[100005],ans[100005];
struct line{
    point st,ed;
}p[100005];
point get_intersection(line s,line t){
    double k=((t.ed-t.st)%(s.st-t.st))/((s.ed-s.st)%(t.ed-t.st));
    return s.st+(s.ed-s.st)*k;
}
bool is_right(point a,line b){
    return (a-b.st)%(b.ed-b.st)>=0;
}
int n,q[100005];
double work(){
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++){
        while(hh+1<=tt&&is_right(get_intersection(p[q[tt]],p[q[tt-1]]),p[i])) tt--; 
        while(hh+1<=tt&&is_right(get_intersection(p[q[hh]],p[q[hh+1]]),p[i])) hh++;
        q[++tt]=i;
    }
    while(hh+1<=tt&&is_right(get_intersection(p[q[tt]],p[q[tt-1]]),p[q[hh]])) tt--; 
    while(hh+1<=tt&&is_right(get_intersection(p[q[hh]],p[q[hh+1]]),p[q[tt]])) hh++;
    q[++tt]=q[hh];
    int k=0;
    for(int i=hh;i<tt;i++)
        ans[++k]=get_intersection(p[q[i]],p[q[i+1]]);
    double res=0;
    for(int i=1;i<=k;i++)
        res+=ans[i]%ans[i%k+1];
    return res==res?fabs(res):0;
}
double check(int mid){
    for(int i=1;i<=n;i++){
        p[i].st=d[i];
        p[i].ed=d[(i+mid-1)%n+1];
    }
    return work();
}
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&d[n-i+1].x,&d[n-i+1].y);
        int l=1,r=((n+1)>>1)+1,mid;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)>1e-8) l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",r);
    }
    return 0;
}