目录
BZOJ1007 水平可见直线题解ｃｏｄｅ
BZOJ1007 水平可见直线
[题目传送门][1]
题解
经典的单调队列进行维护，先将所有的直线以斜率\(A\)为第一关键字，以与\(y\)轴交点高度\(B\)为第二关键字进行排序。考虑加入一条直线，如果斜率与\(A[st[top]]\)相同，那么可以直接弹出队首元素（因为肯定会被覆盖掉）。然后判断该直线与\(st[top-1]\)、\(st[top]\)和\(st[top-1]\)的交点位置，如果该直线与\(st[top-1]\)的交点在\(st[top]\)和\(st[top-1]\)的交点左边，那么可以弹出队首元素（这个思想有点类似与维护凸包），然后将这条直线加入队列。最后留在队列中的直线就是可见的直线。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press return 0 key to continue..."); fgetc(stdin);
const double eps=1e-8;
const int maxn=5e5+500;
struct line {
double a,b;
int idx;
bool operator < (const line &rhs) const {
return fabs(a-rhs.a)<=eps?b<rhs.b:a<rhs.a;
}
}l[maxn];
int n,top;
int res[maxn];
line que[maxn];
/*==================Define Area================*/
double GetPoint(line x1,line x2) {
return (x2.b-x1.b)/(x1.a-x2.a);
}
void Insert(line x) {
while(top) {
if(fabs(que[top].a-x.a)<=eps) top--;
else if(top>1&&GetPoint(x,que[top-1])<=GetPoint(que[top],que[top-1])) top--;
else break;
}
que[++top]=x;
}
int main() {
read(n);
for(int i=1;i<=n;i++) {
scanf("%lf%lf",&l[i].a,&l[i].b);
l[i].idx=i;
}
sort(l+1,l+1+n);
for(int i=1;i<=n;i++) Insert(l[i]);
for(int i=1;i<=top;i++) res[que[i].idx]=1;
for(int i=1;i<=n;i++) {
if(res[i]) printf("%d ",i);
}
return 0;
}
[1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1007
转载于:https://www.cnblogs.com/Apocrypha/p/9433592.html
