[文章目录]
Description
在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.(0 < N < 50000)
维护一个单调栈，类似赛车或者斜率优化。实现将能覆盖的直线都抹去（k相同，b不同）
然后类似斜率优化DP，那两个直线弹掉另一个直线。
（我觉得好像凸包类似吧233）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,tail,z[51000],top;
struct node
{
int k,b,id;
}a[51000];
bool cmp(node x,node y)
{
return x.k==y.k ? x.b<y.b : x.k<y.k;
}
int fuck[50100];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].k,&a[i].b),a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(tail&&a[tail].b<=a[i].b&&a[tail].k==a[i].k) tail--;
a[++tail]=a[i];
}
for(int i=1;i<=tail;i++)
{
while(top>=2&&
1ll*(a[i].b-a[z[top]].b)*(a[z[top-1]].k-a[z[top]].k)
<=
1ll*(a[z[top]].b-a[z[top-1]].b)*(a[z[top]].k-a[i].k)
) top--;
z[++top]=i;
}
for(int i=1;i<=top;i++)
fuck[i]=a[z[i]].id;
sort(fuck+1,fuck+top+1);
for(int i=1;i<=top;i++) printf("%d ",fuck[i]);
return 0;
}