BZOJ 1007 水平可见直线
时间:2019-12-13 09:50:55
收藏:0
阅读:87
题面
题意
??以点斜式给出 \(n\) 条直线,求从 \(y=+\infty\) 处往下看,哪些直线是可见的。
题解
??按斜率升序排序,相同斜率保留最高的,之后用栈来维护可见的直线。
??每次加入新直线时,如果栈顶的两条直线交点不高于直线,说明栈顶的直线已经被新直线和上一条直线完全覆盖,弹出栈顶的直线。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
struct line{
ll a,b,id;
line operator = (const line &l){
a=l.a; b=l.b; id=l.id;
}
};
inline bool cmp(const line &a,const line &b){
if (a.a!=b.a) return a.a<b.a;
if (a.b!=b.b) return a.b>b.b;
return false;
}
inline bool eaq(const line &a,const line &b){
return a.a==b.a;
}
inline bool check(const line &a,const line &b,const line &c){
return (a.b-b.b)*a.a+a.b*(b.a-a.a)<=(a.b-b.b)*c.a+c.b*(b.a-a.a);
}
line a[maxn];
int id[maxn];
int main(){
int i,n,m;
scanf("%d",&n);
for (i=0;i<n;i++){
scanf("%lld%lld",&a[i].a,&a[i].b);
a[i].id=i+1;
}
sort(a,a+n,cmp); n=unique(a,a+n,eaq)-a;
m=0;
for (i=0;i<n;i++){
while (m>1&&check(a[m-2],a[m-1],a[i]))
m--;
a[m++]=a[i];
}
for (i=0;i<m;i++) id[i]=a[i].id;
sort(id,id+m);
for (i=0;i<m;i++) printf("%d ",id[i]);
return 0;
}
原文:https://www.cnblogs.com/Kilo-5723/p/12033375.html
评论(0)