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
-1 0
1 0
0 0
Sample Output
1 2
分析
半平面交的模板题。维护一个栈,把所有边按极角排序后依次插入,每次弹出所有可以被覆盖的直线。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <assert.h>
inline ;
, c = getchar();
x = c - + c - }
;
typedef }line[maxn], St[maxn];
inline getd(N); ;i <= N;++i)
getd(line[i].A), getd(line[i].B), line[i].id = i;
sort(line + , line + N + );
}
;
inline St[it++] = line[];
;i <= N;++i){
].A){
].B)
St[it-] = line[i];
}
){
LL a = (LL)(St[it-].B - St[it-].B) * (line[i].A - St[it-].A);
LL b = (LL)(St[it-].B - line[i].B) * (St[it-].A - St[it-].A);
}
St[it++] = line[i];
}
;
;i <= N;++i)
}
freopen( init();
work();
;
}
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <assert.h>
inline ;
, c = getchar();
x = c - + c - }
;
typedef }line[maxn], St[maxn];
inline getd(N); ;i <= N;++i)
getd(line[i].A), getd(line[i].B), line[i].id = i;
sort(line + , line + N + );
}
;
inline St[it++] = line[];
;i <= N;++i){
].A){
].B)
St[it-] = line[i];
}
){
LL a = (LL)(St[it-].B - St[it-].B) * (line[i].A - St[it-].A);
LL b = (LL)(St[it-].B - line[i].B) * (St[it-].A - St[it-].A);
}
St[it++] = line[i];
}
;
;i <= N;++i)
}
freopen( init();
work();
;
}
半平面交