【BZOJ 1007】 [HNOI2008]水平可见直线

【题目链接】:http://www.lydsy.com/JudgeOnline/problem.php?id=1007

【题意】

【题解】



这个人讲得很好

http://blog.csdn.net/outer_form/article/details/50623551

可以先看一下;

看完之后再看下面的;

根据上面的分析;

可以知道最后所求的线段围成的是一个凹的多边形;

可知相邻的两条边,

它们的交点的横坐标必然是递增的;



如下图;

在把直线按照斜率递增排序之后;

假设第i条直线是可见的;

那么设第i+1条直线(斜率变大了)与第i条直线的交点为A;

然后再设第i+2条直线与第i条直线的交点为B;

上图可以看出;

如果B的横坐标比A的横坐标小,那么i+1就是不可见的了;

相反,第i+2条直线是可见的了;



相反,如上图;

如果B的横坐标比A的横坐标大,

那么i,i+1,i+2就都是可见的了;

根据这个举例；

可以想见;

我们要维护相邻的边的交点的横坐标不下降;

即单调递增;

如果遇到直线i;

crossx(i,sta[top])<=crossx(sta[top],sta[top-1]);

则直接把sta[top]删掉;

因为它不可见了;

直到crossx(i,sta[top])<=crossx(sta[top],sta[top-1])不成立为止;

则在把i加入栈中;

让直线i和直线sta[top-1]相邻;

这样i和sta[top-1]之前的线就都是相邻的了(之前指的是队列的里面的线);

总之就是维护相邻的线的交点的横坐标不下降.

用单调队列搞就好.



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const double eps = 1e-8;

const int N = 5e4+100;

struct node

{

    double k,a;

    int id;

};

node bian[N],sta[N],zhan[N];

int n,tn,top;

bool bo[N];

bool cmp(node a,node b)

{

    if (fabs(a.k-b.k)<eps)

        return a.a>b.a;

    else

        return a.k < b.k;

}

/*

    y1 = k1x+b1

    y2 = b2x+b2

*/

double crossx(node a,node b)

{

    double k1 = a.k,k2 = b.k,b1 = a.a,b2 = b.a;

    return (b2-b1)/(k1-k2);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);

    rep1(i,1,n)

    {

        scanf("%lf%lf",&bian[i].k,&bian[i].a);

        bian[i].id = i;

    }

    sort(bian+1,bian+1+n,cmp);

    tn = n;

    n = 1;

    sta[1] = bian[1];

    rep1(i,2,tn)

        if (fabs(bian[i].k-bian[i-1].k)>eps)

            sta[++n] = bian[i];

    rep1(i,1,n)

    {

        while (top)

        {

            if (top>1 && crossx(sta[i],zhan[top-1])<=crossx(zhan[top],zhan[top-1]))

                top--;

            else

                break;

        }

        zhan[++top] = sta[i];

    }

    rep1(i,1,top)

        bo[zhan[i].id] = 1;

    n = tn;

    rep1(i,1,n)

        if (bo[i])

            printf("%d ",i);

    return 0;

}