BZOJ1007 [HNOI2008]水平可见直线 【计算几何+单调栈】

tonyfang posted @ 2015年8月27日 22:09 in BZOJ with tags c++ OI , 203 阅读

我们先按照斜率排个序,然后顺次将直线压入栈中。

设栈顶元素$top$,栈顶元素的前一个元素为$top-1$,即将压入栈的元素为$t$,那么,如果$top$与$t$的交点的横坐标比$top-1$和$top$交点的横坐标小的话,弹出栈。正确性可脑补。

 

# include <stdio.h>
# include <algorithm>
# include <string.h>

using namespace std;
struct lines {
	int A,B,C;
	bool operator ==(const lines &b) {return A==b.A;}
}s[50010],a[50010];
int n,nn,top=1;int gg[50010];
inline int cmp(lines _a,lines _b) {
	return _a.A < _b.A || (_a.A == _b.A && _a.B > _b.B);
}
inline double g(lines x,lines y) {
	return (double)(y.B-x.B)/(double)(x.A-y.A);
}
int main() {
	scanf("%d",&n);nn=n;
	for (int i=1;i<=n;++i) {
		scanf("%d%d",&a[i].A,&a[i].B);
		a[i].C=i;
	}
	sort(a+1,a+n+1,cmp);
	n = unique(&a[1],&a[n+1])-&a[1];
	for (int i=1;i<=n;++i) {
		while(top > 2 && g(s[top-1],s[top-2]) - g(s[top-1], a[i]) > -1*1e-8) top--;
		s[top++]=a[i];
	}
	memset(gg,0,sizeof(gg));
	for (int i=1;i<top;++i) gg[s[i].C]=1;
	for (int i=1;i<=nn;++i) if(gg[i]) printf("%d ",i);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter