洛谷P3194 [HNOI2008]水平可见直线 题解
题意:在$ x-y$ 直角坐标平面上有 \(n\) 条直线 \(L_1,L_2,…L_n\),若在 \(y\) 值为正无穷大处往下看,能见到 \(L_i\) 的某个子线段,则称 \(L_i\) 为可见的,否则 \(L_i\) 为被覆盖的。 例如,对于直线: \(L_1:y=x\); \(L_2:y=-x\); \(L_3:y=0\); 则 \(L_1\) 和 \(L_2\) 是可见的,\(L_3\) 是被覆盖的。给出 \(n\) 条直线,表示成 \(y=Ax+B\) 的形式(\(|A|,|B| \le 500000\)),且 \(n\) 条直线两两不重合,求出所有可见的直线。
一条直线C被另外两条直线A和B所覆盖
它的充分必要条件为直线C在A,B交点处的值更小一些
反之,直线C也可能对答案有贡献
那么交点的坐标是什么呢? \[ A_1x+B_1=A_2x+B_2\\ x=\dfrac{B_2-B_1}{A_1-A_2} \] 则 \[ A_1\dfrac{B_2-B_1}{A_1-A_2} + B_1 \ge A_3\dfrac{B_2-B_1}{A_1-A_2} + B_3\\ \color{red}{\dfrac{B_2-B_1}{A_2-A_1}\ge\dfrac{B_3-B_1}{A_3-A_1}} \] 可以发现这个式子很像斜率
如果记 \(P_i(A_i,B_i)\)
那么答案就是点集 \(\{P_i\}\) 构成的上凸壳
为什么是上凸壳?显然我们选定的是斜率大且尽可能截距大
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
struct vct
{
double x,y;int id;
vct operator-(const vct &o)const
{
return (vct){x-o.x,y-o.y};
}
}p[N];
int n,stk[N],top;
double cross(vct a,vct b)
{
return a.x*b.y-a.y*b.x;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> p[i].x >> p[i].y;
p[i].id=i;
}
sort(p+1,p+1+n,[](vct a,vct b)
{
return a.x==b.x?a.y>b.y:a.x>b.x;
});
stk[++top]=1;
for(int i=2; i<=n; i++)
{
if(p[i-1].x==p[i].x)continue;
while(top>1&&cross(p[stk[top]]-p[stk[top-1]],p[i]-p[stk[top]])<=0)
--top;
stk[++top]=i;
}
sort(stk+1,stk+1+top,[](int a,int b)
{
return p[a].id<p[b].id;
});
for(int i=1; i<=top; i++)
cout << p[stk[i]].id << " ";
return 0;
}