【题目描述】 在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条直线两两不重合.求出所有可见的直线。 【输入格式】 第一行为N(0 < N < 50000) 接下来的N行输入Ai,Bi 【输出格式】 从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格 【样例输入】 3 -1 0 1 0 0 0 【样例输出】 1 2 【分析】 如果只有1条直线就太简单了，肯定可以看见。 如果有2条直线，也不难解决，如果两直线平行就遮住了一条，反之都能看见。 接下来的分析不考虑平行。 如果有3条直线，会组成一个三角形，不难发现三角形底边所在直线被遮住了。于是可以得出结论：若斜率最大的直线与斜率次大（或次次大）的直线的交点在斜率次大和斜率次次大的直线的交点的左边，则斜率次大的直线被覆盖。 于是可以得出算法：先把所有直线按斜率排序，然后枚举斜率次次大的直线，分别求出与斜率最大和次大的直线的交点，看交点的位置。 可以用栈来维护，有覆盖的就直接弹栈。最后栈里存放的直线就是没有被覆盖的。 至于求交点，可以列方程组： A1x+B1=y A2x+B2=y 然后解一下就可以。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; struct Line { int k,b,i;//k表示斜率，b表示截距，i表示序号 bool operator < (const Line& rhs) const//重载运算符“<” { if (k==rhs.k) return b>rhs.b; return k<rhs.k; } } line[50001]; int stack[50001]={0},ans[50001]; double find_intersection_point(int i,int j) { int k1=line[i].k, b1=line[i].b, k2=line[j].k, b2=line[j].b; return (double)(b2-b1)/(k1-k2);//求交点，方程不解释 } int main() { int n,top=1; scanf("%d",&n); if (n==1) { printf("1 \n");return 0; }//特判 for (int i=0;i<n;i++) { int k,b; scanf("%d%d",&k,&b); line[i]=(Line){k,b,i+1}; } sort(line,line+n);//排序 //其实这里少了一步stack[0]=0，即斜率最大的直线先进栈，但是不影响结果 if (line[1].k!=line[0].k) stack[top++]=1;//若两直线不平行则斜率次大的进栈 for (int i=2;i<n;i++) { if (line[i].k==line[i-1].k) continue;//平行肯定覆盖了 while (top>1 && find_intersection_point(i,stack[top-1])-find_intersection_point(stack[top-2],stack[top-1])<=1e-6) top--;//判断交点 stack[top++]=i;//入栈 } for(int i=0;i<top;i++) ans[i]=line[stack[i]].i;//找到栈中的直线编号 sort(ans,ans+top);//栈里的直线不一定是按编号递增排列的 for(int i=0;i<top;i++) printf("%d ",ans[i]); return 0; }转载于:https://www.cnblogs.com/JRX2015U43/p/6533478.html
