bzoj 1007: [HNOI2008]水平可见直线【半平面交】

其实并不算标准半平面交？但是思路差不多

先按照斜率排序，然后用栈维护凸壳，每遇到重斜率或a[i],s[top-1]交点的x轴在s[top],s[top-1]交点左侧，则说明s[top]被a[i],s[top-1]覆盖，弹栈即可；

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=50005;

const double eps=1e-8;

int n,top;

bool v[N];

struct qwe

{

	double a,b;

	int id;

}a[N],s[N];

int sgn(double x)

{

	return x<-eps?-1:x>eps;

}

bool cmp(const qwe &a,const qwe &b)

{

	return sgn(a.a-b.a)==0&&a.b<b.b||a.a<b.a;

}

double jdy(qwe a,qwe b)

{

	return (b.b-a.b)/(a.a-b.a);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lf%lf",&a[i].a,&a[i].b),a[i].id=i;

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++)

	{

		// while(top>1&&(sgn(jdy(s[top],s[top-1])-jdy(a[i],s[top-1]))>=0||sgn(s[top].a-a[i].a)==0))

			// top--;

		while(top)

		{

			if(sgn(s[top].a-a[i].a)==0)

				top--;

			else if(top>1&&jdy(a[i],s[top-1])<=jdy(s[top],s[top-1]))

				top--;

			else

				break;

		}

		s[++top]=a[i];

	}

	for(int i=1;i<=top;i++)

		v[s[i].id]=1;

	for(int i=1;i<=n;i++)

		if(v[i])

			printf("%d ",i);

	return 0;

}

巴特西

bzoj 1007: [HNOI2008]水平可见直线【半平面交】

最新文章

热门文章