题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1007
洛谷:https://www.luogu.com.cn/problem/P3194
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条直线两两不重合.求出所有可见的直线.
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3-1 0
1 0
0 0
Sample Output
1 2把所有的直线按k递增为第一关键字,b递减为第二关键字排序。因为所有可见的直线一定能组成一个类似下凸的形状。
然后逐个压入栈中,压栈之前把这条直线能覆盖的直线都弹出,既只要这条直线与sta[top-1]的交点在sta[top]与sta[top-1]的交点左边,则sta[top]就一定被这条直线覆盖了。
计算交点只需要计算x的坐标就行了那么$a_{1}x+b_{1}=a_{2}x+b_{2}$很容易得到$x=\frac{b_{2}-b_{1}} {a_{1}-a_{2}}$
以下是AC代码:
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int mac=5e4+10; struct line { double a,b; int id; bool operator <(const line &s)const{ if (a==s.a) return b>s.b; return a<s.a; } }; double cross(line y1,line y2) { return (y1.b-y2.b)/(y2.a-y1.a); } line stk[mac],ln[mac]; int nb[mac]; int main() { int n; scanf ("%d",&n); for (int i=1; i<=n; i++){ ln[i].id=i; scanf("%lf%lf",&ln[i].a,&ln[i].b); } sort(ln+1,ln+n+1); int top=0; for (int i=1; i<=n; i++){ if (top<1) {stk[++top]=ln[i];continue;} if (ln[i].a==stk[top].a) continue;//由于是按照截距从大到小的,斜率一样的情况下截距大的会覆盖小的 while (top>1 && cross(ln[i],stk[top-1])<=cross(stk[top-1],stk[top])) top--;//top必须设置为大于一,因为等于1的时候top-1并不存在,就会导致答案出错 stk[++top]=ln[i]; } for (int i=1; i<=top; i++) nb[i]=stk[i].id; sort(nb+1,nb+1+top); for (int i=1; i<=top; i++) printf ("%d%c",nb[i],i==top?'\n':' '); return 0; }