BZOJ1007: [HNOI2008]水准可见直线

BZOJ1007: [HNOI2008]水平可见直线

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2941  Solved: 1037
[Submit][Status]

Description

Input

Output

Sample Input

Sample Output

参考了WYL8899大犇的题解之后懂了

按斜率排序，用栈维护可见直线。

如右图，当前考虑直线now，栈顶top，栈顶的下一个元素top'大致的位置。

显然now和top'将把top完全遮盖。

思考一下可以得出，记两直线交点的横坐标为x(A,B)，则x(now,top)<=x(top,top')时，栈顶直线被废，弹出栈。

反复这样操作，直至不满足上面的条件，将当前直线压入栈中。

最后在栈中的直线就是答案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
       int a,b,id;
       }l[60000];
bool f[60000];
int n,i,top,stack[60000];
 
bool cmp(node a,node b)
{
     if (a.a == b.a) return (a.b > b.b);
     return (a.a < b.a);
}
 
bool check(node a,node b,node c)
{
     double t1=(double)(b.b-a.b),t2=(double)(a.a-b.a),t3=(double)(c.b-b.b),t4=(double)(b.a-c.a);
     double x1=(double) t1/t2;
     double x2=(double) t3/t4;
     if (x1<=x2) return true;
     return false;
}
 
int main()
{
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%d%d",&l[i].a,&l[i].b);
        l[i].id=i;
    }
    sort(l+1,l+n+1,cmp);
    for (i=1; i<=n; i++)
    {
        if (l[i].a==l[i-1].a) continue;
        while (top>=2 && check(l[i],l[stack[top]],l[stack[top-1]])) top--;
        stack[++top]=i;
    }
    memset(f,false,sizeof(f));
    for (i=1; i<=top; i++)                                    
        f[l[stack[i]].id]=true;
    for (i=1; i<=n; i++)
        if (f[i]) printf("%d ",i);
    return 0;
}