描述 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 条直线两两不重合. 求出所有可见的直线.
第一行为 N(0 < N < 50000), 接下来的 N 行输入 Ai,Bi
从小到大输出可见直线的编号，两两中间用空格隔开, 最后一个数字后面也必须有个空格
3
-1 0
1 0
0 0
样例输出 SampleOutput
1 2
BZOJ 1007
按照斜率从小到大（截距从大到小）排序，若直线 a 与 b 的交点横坐标大于等于直线 b 与 c 的交点（a #include #include #include #include #include using namespace std; const int maxn=50005; int i,j,t,n,m,l,r,k,z,y,x; struct line { int a,b,id; bool operator < (const line& tmp) const { return (a==tmp.a)?((b==tmp.b)?(id<tmp.id):(b>tmp.b)):(a<tmp.a); } }a[maxn]; vector s; vector ::iterator si; inline bool comp(line a,line b) { return a.id<b.id; } inline double crossx(line a,line b) { return (double)(a.b-b.b)/(double)(b.a-a.a); } int main() { scanf(“%d”,&n); for (i=1;i<=n;i++) scanf(“%d%d”,&a[i].a,&a[i].b),a[i].id=i; sort(a+1,a+n+1); s.clear(); for (i=1;i<=n;i++) { if (!s.empty() && a[i].a==s.back().a) continue; while (s.size()>1 && crossx(a[i],s.back())<=crossx(s.back(),s.at(s.size()-2))) s.pop_back(); s.push_back(a[i]); } sort(s.begin(),s.end(),comp); for (si=s.begin();si!=s.end();si++) printf(“%d”,(*si).id); printf(“”); return 0; } ```