bzoj千题计划210：bzoj2642 | Poj3968 | UVALive 4992| hdu 3761 Jungle Outpost

http://www.lydsy.com/JudgeOnline/problem.php?id=2642

题意：

n个瞭望台，形成一个凸n边形。这些瞭望台的保护范围是这个凸包内的任意点。

敌人进攻时，会炸毁一些瞭望台，使得总部暴露在新的保护范围之外。

选择一个点作为总部，使得敌人在任何情况下需要炸坏的瞭望台数目尽量多

任何情况指，假设需炸毁m个，无论炸毁哪m个，剩下的瞭望台都不能保护总部

输出这个数目

凸壳上的点顺时针输入

若敌人只能炸一次，那么总部应选在

所有点i+2到点i组成的有向直线的左侧——半平面交

若敌人能炸两次，那么炸连续的两个点更优

炸毁连续的两个，可以使得到的半平面的左侧尽量靠边

这样交集更容易为空

同理，炸毁k个也是炸毁连续的k个

所以二分炸毁次数k，

判断所有i+k+1和点i构成的有向直线表示的半平面有没有交集即可

#include<cmath>

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 50001

typedef long long LL;

const double eps=1e-;

struct Point

{

    double x,y;

    Point(double x=,double y=):x(x),y(y) {}

};

typedef Point Vector;

Point P[N];

Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }

Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

Vector operator * (Vector A,double b) { return Vector(A.x*b,A.y*b); }

struct Line

{

    Point P;

    Vector v;

    double ang;

    Line() {}

    Line(Point P,Vector v) : P(P),v(v) { ang=atan2(v.y,v.x); }

    bool operator < (Line L) const

    {

        return ang<L.ang;

    }

};

Line L[N];

void read(int &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

double Cross(Vector A,Vector B)

{

    return A.x*B.y-A.y*B.x;

}

bool OnLeft(Line L,Point p)

{

    return Cross(L.v,p-L.P)>;

}

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;

}

bool HalfplaneIntersection(Line *L,int n)

{

//    sort(L,L+n);  顺时针输入的点，本来就按极角排好序了

    Point *p=new Point[n];

    Line *q=new Line[n];

    int first,last;

    q[first=last=]=L[];

    for(int i=;i<n;++i)

    {

        while(first<last && !OnLeft(L[i],p[last-])) last--;

        while(first<last && !OnLeft(L[i],p[first])) first++;

        q[++last]=L[i];

        if(fabs(Cross(q[last].v,q[last-].v))<eps)

        {

            last--;

            if(OnLeft(q[last],L[i].P)) q[last]=L[i];

        }

        if(first<last) p[last-]=GetIntersection(q[last],q[last-]);

    }

    while(first<last && !OnLeft(q[first],p[last-])) last--;

    return last-first>;

}

bool check(int n,int k)

{

    int m=;

    for(int i=;i<n;++i) L[m++]=Line(P[i],P[i]-P[(i+k+)%n]);

    return !HalfplaneIntersection(L,m);

}

int main()

{

    int n,x,y;

    int l,r,mid,ans=;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=;i<n;++i)

        {

            read(x); read(y);

            P[i]=Point(x,y);

        }

        ans=n-;

        l=; r=n-;

        while(l<=r)

        {

            mid=l+r>>;

            if(check(n,mid)) ans=mid,r=mid-;

            else l=mid+;

        }

        cout<<ans<<'\n';

    }

}

巴特西

bzoj千题计划210：bzoj2642 | Poj3968 | UVALive 4992| hdu 3761 Jungle Outpost

最新文章

热门文章