首页 > 代码库 > 1007: [HNOI2008]水平可见直线[维护下凸壳]
1007: [HNOI2008]水平可见直线[维护下凸壳]
1007: [HNOI2008]水平可见直线
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 7184 Solved: 2741
[Submit][Status][Discuss]
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
HINT
Source
#include<cstdio>#include<algorithm>using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int N=5e5+5;struct node{int a,b,id;}c[N];int n,cnt,pos[N];double slop[N];bool vis[N];bool operator <(const node &x,const node &y){ return x.a<y.a;}int main(){ n=read(); for(int i=1;i<=n;i++) c[i].a=read(),c[i].b=read(),c[i].id=i; sort(c+1,c+n+1); int now=1; for(int i=2;i<=n;i++){ for(;c[i].a==c[now].a;i++){ if(c[i].b>c[now].b){ c[now]=c[i]; } } if(i<=n) c[++now]=c[i]; } pos[cnt=1]=1;slop[1]=-0x7fffffffffffffffLL; for(int i=2;i<=now;i++){ double low; for(;;){//相对斜率关系(避免求交点) low=(double)(c[pos[cnt]].b-c[i].b)/(double)(c[i].a-c[pos[cnt]].a); if(low<=slop[cnt]) cnt--; else break; } pos[++cnt]=i; slop[cnt]=low; } for(int i=1;i<=cnt;i++) vis[c[pos[i]].id]=1; for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i); return 0;}
1007: [HNOI2008]水平可见直线[维护下凸壳]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。