水平可见直线
【问题描述】
在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.对于斜率不同的三条直线，如果一条直线不可见
那么必定是斜率最大和斜率最小的覆盖另外一条线段
同时斜率最大和斜率最小的直线的交点在另一条线段的上方
根据这个性质，通过排序和单调栈即可维护可见直线。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = , s = ;
char c = getchar();
while('' > c || c > '')
{
if(c == '-') s = -;
c = getchar();
}
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x * s;
}
int n;
struct shape
{
int a, b, i;
};
shape a[];
int s[];
int ans[];
inline bool rule(shape a, shape b)
{
if(a.a != b.a) return a.a > b.a;
return a.b > b.b;
}
inline double Sol(int x, int y)
{
return (double) (a[y].b - a[x].b) / (double) (a[x].a - a[y].a);
}
int main()
{
n = Get();
for(int i = ; i <= n; ++i)
{
a[i].a = Get();
a[i].b = Get();
a[i].i = i;
}
sort(a + , a + + n, rule);
int top = ;
for(int i = ; i <= n; ++i)
{
if(a[i].a == a[s[top]].a) continue;
while(top > && Sol(s[top], i) >= Sol(s[top], s[top - ]))
--top;
s[++top] = i;
ans[top] = a[i].i;
}
sort(ans + , ans + + top);
for(int i = ; i <= top; ++i) printf("%d ", ans[i]);
}