首页 > 其他分享 >【瞎口胡】半平面交

【瞎口胡】半平面交

时间:2022-12-07 20:46:18浏览次数:56  
标签:直线 ab return 瞎口 inline 平面 CP Cro

顾名思义,用于求解若干半平面的交。

在 OI 中,一般有如下的应用情形:给定若干条直线,求它们的左边组成的半平面的交。

事实上,我们可以通过一组点集来描述半平面交:这是因为如果半平面交的面积有限,那么它一定是凸多边形。证明可以考虑找到多边形中一个大于 \(180\) 度的角,然后很容易发现这是不符合条件的。

流程

考虑构造半平面交。我们将所有直线极角排序,然后依次加入。我们维护一个双端队列表示当前构成半平面交的直线。

一般来讲,加入一条直线,我们无事发生:

image

它会和之前的直线(黑色)一起构成当前的半平面交。

但意外总会发生。

image

如图,当前队尾的两条直线的交点在红色直线的右侧。此时我们可以断定,队尾的直线对构成半平面交没有贡献,因为红色的限制严格强于它。因此,我们 Pop 掉队尾的直线。

不止队尾,队首的直线可能也会被 Pop 掉。

image

只需要判定队首两条直线的交点是否在红色直线右侧。

另外,加完所有直线后,还应该依次判定队尾两条直线的交点是否在队首直线的左侧,如果是,则 Pop 队尾。原因很简单,加入直线时,前面的直线受后面直线约束,但后面的直线不受前面直线的约束。但它们连成的是一个环,因此队尾的直线是要受到队首直线约束的。

注意事项

我们操作时应该先 Pop 队尾再 Pop 队首,原因见 OI-Wiki

如果有多个共线的直线,我们应该直接最左侧的。实现细节见代码。

# include <bits/stdc++.h>
# define Vector Point
# define DB double
# define CP const Point
# define CV const Vector
const int N=100010,INF=0x3f3f3f3f;
const DB eps=1e-8;
const DB Pi=acos(-1);
struct Point{
	DB x,y;
	Point(DB X=0,DB Y=0){
		x=X,y=Y;
		return;
	}
};
struct dLine{
	Point s,t;
	double an;
};
dLine que[N];
typedef std::vector <Point> Poly;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline int Sign(DB x){
	return (x<-eps)?-1:((x>eps)?1:0);
}
inline bool x_comp(CP &a,CP &b){
	return (Sign(a.x-b.x))?(a.x<b.x):(a.y<b.y);
}
inline DB Fabs(DB x){
	return x*Sign(x);
}
inline DB Dot(CV &u,CV &v){
	return u.x*v.x+u.y*v.y;
}
inline DB Cro(CV &u,CV &v){
	return u.x*v.y-u.y*v.x;
}
inline DB Len(CV &u){
	return sqrt(Dot(u,u));
}
Vector operator - (CV &u,CV &v){
	return Vector(u.x-v.x,u.y-v.y);
}
Vector operator + (CV &u,CV &v){
	return Vector(u.x+v.x,u.y+v.y);
}
Vector operator * (CV &u,DB k){
	return Vector(u.x*k,u.y*k);
}
bool operator == (CP &u,CP &v){
	return !(Sign(u.x-v.x)||Sign(u.y-v.y)); 
} 
inline Point PointTurn(CP &u,DB theta){
	return Point(u.x*cos(theta)+u.y*sin(theta),-u.x*sin(theta)+u.y*cos(theta));
}
inline Point PointTurn(CP &u,DB theta,CP &c){
	return Point((u.x-c.x)*cos(theta)+(u.y-c.y)*sin(theta)+c.x,-(u.x-c.x)*sin(theta)+(u.y-c.y)*cos(theta)+c.y);
}
inline bool PointonSeg(CP &u,CP &a,CP &b){
	return !Sign(Cro(u-a,u-b))&&(Dot(u-a,u-b)<=0);
}
inline bool DistoSeg(CP &u,CP &a,CP &b){
	if(a==b)
		return Len(u-a);
	Vector au=u-a,bu=u-b,ab=b-a;
	if(Sign(Dot(au,ab))<0)
		return Len(au);
	if(Sign(Dot(bu,ab))>0)
		return Len(bu);
	return Fabs(Cro(au,ab)/Len(ab));
}
inline bool PointonLine(CP &u,CP &a,CP &b){
	return !Sign(Cro(u-a,u-b));
}
inline Point FootPoint(CP &u,CP &a,CP &b){
	Vector au=u-a,bu=u-b,ab=b-a;
	DB aulen=Dot(au,ab)/Len(ab),bulen=-1.0*Dot(bu,ab)/Len(ab);
	return a+ab*(aulen/(aulen+bulen));
}
inline Point SymPoint(CP &u,CP &a,CP &b){
	return u+(FootPoint(u,a,b)-u)*2;
}
inline Point CrossLL(CP &a,CP &b,CP &c,CP &d){
	Vector ab=b-a,cd=d-c,ca=a-c;
//	printf("%.8lf\n",Cro(ab,cd));
//	if(Sign(Cro(ab,cd))==0)
//		printf("warning\n");
	return a+ab*(Cro(cd,ca)/Cro(ab,cd));
}
inline bool CrossLS(CP &a,CP &b,CP &c,CP &d){
	return (PointonLine(CrossLL(a,b,c,d),c,d));
}
inline bool CrossSS(CP &a,CP &b,CP &c,CP &d){
	DB ab_c=Cro(b-a,c-a),ab_d=Cro(b-a,d-a);
	DB cd_a=Cro(d-c,a-c),cd_b=Cro(d-c,b-c);
	return (Sign(ab_c)*Sign(ab_d)<0)&&(Sign(cd_a)*Sign(cd_b)<0);
}
inline DB PolyArea(Poly &P){
    if(P.size()<=2) return 0;
	DB res=0;
	for(int i=0;i<(int)P.size();++i){
		res+=Cro(P[i],P[(i+1)%P.size()]);
	}
	return res/2.0;
}
inline void ConvexHull(Poly &P,Poly &ans){
	int n=P.size();
	std::sort(P.begin(),P.end(),x_comp);
	ans.resize(0);
	int siz=0;
	for(int i=0;i<n;++i){
		while(siz>1&&Sign(Cro(ans[siz-1]-ans[siz-2],P[i]-ans[siz-2]))<=0)
			--siz,ans.pop_back();
		ans.push_back(P[i]),++siz;
	}
	for(int i=n-1,st=siz;i>=0;--i){
		while(siz>st&&Sign(Cro(ans[siz-1]-ans[siz-2],P[i]-ans[siz-2]))<=0)
			--siz,ans.pop_back();
		ans.push_back(P[i]),++siz;
	}
	ans.pop_back();
	return;
}
inline DB PolyDiameter(Poly &P){
	int n=P.size();
	if(P.size()<2)
		return 0;
	if(P.size()==2)
		return Len(P[0]-P[1]);
	int now=2;
	DB res=0;
	P.push_back(P[0]);
	for(int i=0;i<n;++i){
		while(Sign(Cro(P[i+1]-P[i],P[now]-P[i])-Cro(P[i+1]-P[i],P[now+1]-P[i]))<0)
			now=(now+1)%n;
		res=std::max(res,std::max(Len(P[now]-P[i]),Len(P[i+1]-P[i])));
	}
	P.pop_back();
	return res;
}
inline bool DvecComp(const dLine &u,const dLine &v){
	if(Sign(u.an-v.an)){
		return Sign(u.an-v.an)==-1;
	}
	return Sign(Cro(u.t-u.s,v.t-u.s))==1; // 如果 v 在 u 的左边,则叉积>0,u 排在 v 之前
}
inline bool AngleCheck(const dLine &u,const dLine &v,const dLine &z){ // check if uv at the right of z
	Point cro=CrossLL(u.s,u.t,v.s,v.t);
	return Sign(Cro(cro-z.s,z.t-z.s))==1;
}
inline Poly HalfPlane(std::vector <dLine> &Lines){
	int siz=Lines.size();
	for(int i=0;i<siz;++i){
		Lines[i].an=atan2(Lines[i].t.y-Lines[i].s.y,Lines[i].t.x-Lines[i].s.x);
	}
	std::sort(Lines.begin(),Lines.end(),DvecComp); // 极角排序
	Poly ans;
	int l=1,r=0;
	for(int i=0;i<siz;++i){
		while(l<r&&AngleCheck(que[r-1],que[r],Lines[i]))
			--r;
		while(l<r&&AngleCheck(que[l],que[l+1],Lines[i]))
			++l;
		que[++r]=Lines[i];
		if(l<r&&!Sign(Cro(que[r].t-que[r].s,que[r-1].t-que[r-1].s))) // 平行时,一定是后面的直线更靠左
			--r,que[r]=Lines[i]; // 将原来的直线更换为自己,队列长度 --
	}
	while(l<r&&AngleCheck(que[r-1],que[r],que[l])) // 检查队尾
		--r;
	for(int i=l;i<r;++i)
		ans.push_back(CrossLL(que[i].s,que[i].t,que[i+1].s,que[i+1].t));
	ans.push_back(CrossLL(que[r].s,que[r].t,que[l].s,que[l].t));
	return ans;
}
int main(void){
	std::vector <dLine> S;
	Poly P;
	int T=read(),n;
	while(T--){
		n=read();
		P.clear();
		for(int i=1;i<=n;++i){
			int x=read(),y=read();
			P.push_back((Point){1.0*x,1.0*y});
		}
		for(int i=0;i<(int)P.size();++i){
			S.push_back((dLine){P[i],P[(i+1)%P.size()],0.0});
		}
	}
	Poly res=HalfPlane(S);
	printf("%.3lf",PolyArea(res));
	return 0;
}

标签:直线,ab,return,瞎口,inline,平面,CP,Cro
From: https://www.cnblogs.com/liuzongxin/p/16964474.html

相关文章

  • 300014 平面立面剖面三图和详图
    <?phpheader('Content-Type:text/html;charset=utf-8');define('ROOT',$_SERVER['DOCUMENT_ROOT']);includeROOT.'/assets/php/head.php';$tit='平面立面剖面三......
  • 【DSY】直线 题解(平面分块)
    Link.平面分块。Solution直接观察题面可以发现,这道题实在没有什么高深的技巧性可言。于是我们直接暴力:分块。然后wjy大佬表示,这个做法有着二维线段树的思想。下面......
  • 折线分割平面
    ​描述我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平......
  • Kubernetes 控制平面组件:API Server
    一、APIServer的概念kube-apiserver是Kubernetes最重要的核心组件之一,主要提供以下的功能:  提供集群管理的RESTAPI接口,包括认证授权、数据校验以及集群......
  • HDU-1007 Quoit Design [平面最近点对]
    QuoitDesignTimeLimit:10000/5000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):86145    AcceptedSubmission(s):......
  • 3d激光雷达开发(平面分割)
        平面分割是点云数据经常需要处理的一个功能。在很多场景下面,平面数据都是没有用的。这个时候需要考虑的,就是怎么把平面数据从点云当中分割出去。鉴于此,pcl库给......
  • Kubernetes 1.25.4数据平面自带nginx负载均衡实现高可用
    1、环境准备要点:1、使用一个FQDN统一作为APIServer的接入点;2、加入集群之前,每个节点都将该FQDN解析至第一个Master;3、加入集群之后,每个Master节点将该FQDN都解析至自身......
  • OpenCV提取图像的位平面
    提取位平面函数(仅仅支持灰度图像)defextractBitPlace(img,layer):h,w=img.shapemat=np.ones((h,w),np.uint8)mat=mat*(2**(layer-1))returncv2.bitw......
  • SVM 超平面计算例题
    SVMSummaryExampleSupposethedatasetcontainstwopositivesamples\(x^{(1)}=[1,1]^T\)and\(x^{(2)}=[2,2]^T\),andtwonegativesamples\(x^{(3)}=[0,0]^T\)......
  • SVM 超平面计算例题
    SVMSummaryExampleSupposethedatasetcontainstwopositivesamples\(x^{(1)}=[1,1]^T\)and\(x^{(2)}=[2,2]^T\),andtwonegativesamples\(x^{(3)}=[0,0]^T\)......