时间戳

首页 > 技术文章 > [HDU4316]Mission Impossible（计算几何/凸包/半平面交）

[HDU4316]Mission Impossible（计算几何/凸包/半平面交）

LanrTabe 2019-07-27 11:08 原文

题目链接：

HDU4316

计算几何太duliu了~

题目大意：空间中有一个物体，上空有\(3\)个摄像头拍摄地面，求摄像头公共盲区面积大小

首先求出每一个摄像头的盲区：

将物体的每一个点投影到地面再求凸包即可。

然后将\(3\)个凸包的每一条边都拿来一起做一次半平面交，求出公共盲区

最后三角剖分求面积就好了。

代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

const double Eps=1e-8;
inline double Abs(double x){return x>=0?x:-x;}
inline int Sign(double x){return Abs(x)<Eps?0:(x>0?1:-1);}

typedef struct Point
{
	double x,y;
	inline Point operator+(Point o){return (Point){x+o.x,y+o.y};}
	inline Point operator-(Point o){return (Point){x-o.x,y-o.y};}
	inline Point operator*(double k){return (Point){x*k,y*k};}
	inline bool operator<(Point o){return Sign(x-o.x)?x<o.x:y<o.y;}
	inline bool operator==(Point o){return !Sign(x-o.x)&&!Sign(y-o.y);}
}Vector;
inline double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
inline double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

struct Point_3D{double x,y,z;};
inline Point Projection(Point Light,Point_3D Object)//Object在Light下的投影
{return Light+((Vector){Object.x,Object.y}-Light)*(100/(100-Object.z));}

struct Line
{
	Point p;Vector v;double Ang;Line(){}
	Line(Point ps,Vector vs):p(ps),v(vs){Ang=atan2(v.y,v.x);}
	inline bool operator<(Line o){return Ang<o.Ang;}
};

Point_3D Mac[105];//机器坐标
Point Camera[5];//摄像头坐标

Point S[105];
std::vector<Point> Convex_Hull(std::vector<Point> p)//求凸包
{
	std::vector<Point> Ans;
	std::sort(p.begin(),p.end());
	int n=std::unique(p.begin(),p.end())-p.begin(),Sn=0;
	for(int i=0;i<=n-1;S[++Sn]=p[i++])
		while(Sn>=2&&Sign(Cross(p[i]-S[Sn-1],S[Sn]-S[Sn-1]))<0)--Sn;
	for(int i=1;i<Sn;++i)Ans.push_back(S[i]);
	Sn=0;
	for(int i=n-1;i>=0;S[++Sn]=p[i--])
		while(Sn>=2&&Sign(Cross(p[i]-S[Sn-1],S[Sn]-S[Sn-1]))<0)--Sn;
	for(int i=1;i<Sn;++i)Ans.push_back(S[i]);
	return Ans;
}

inline bool OnLeft(Point p,Line l){return Sign(Cross(p-l.p,l.v))==-1;}//点p是否在线l左侧
inline Point CrossP(Line A,Line B){return A.p+A.v*(Cross(B.v,A.p-B.p)/Cross(A.v,B.v));}//直线交点

Point P[305];
Line Q[305];
std::vector<Point> HPI(std::vector<Line> L)//半平面交
{
	std::sort(L.begin(),L.end());
	int n=L.size(),Qh=0,Qt=0;
	Q[0]=L[0];
	for(int i=1;i<n;++i)
	{
		while(Qh<Qt&&!OnLeft(P[Qt-1],L[i]))--Qt;
		while(Qh<Qt&&!OnLeft(P[Qh],L[i]))++Qh;
		if(Sign(Cross(L[i].v,Q[Qt].v)))Q[++Qt]=L[i];
		else if(OnLeft(L[i].p,Q[Qt]))Q[Qt]=L[i];
		if(Qh<Qt)P[Qt-1]=CrossP(Q[Qt-1],Q[Qt]);
	}
	while(Qh<Qt&&!OnLeft(P[Qt-1],Q[Qh]))--Qt;
	std::vector<Point> Ans;
	if(Qt-Qh<=1)return Ans;//没有公共区域
	P[Qt]=CrossP(Q[Qh],Q[Qt]);
	for(int i=Qh;i<=Qt;++i)Ans.push_back(P[i]);
	return Ans;
}

double Area(std::vector<Point> Poly)//求多边形面积
{
	double Sum=0;
	int n=Poly.size();
	for(int i=0;i<n;++i)Sum+=Cross(Poly[i],Poly[(i+1)%n]);
	return Sum/2;
}

int main()
{
	//freopen("in.txt","r",stdin);
	for(int n;~scanf("%d",&n);)
	{
		for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&Mac[i].x,&Mac[i].y,&Mac[i].z);
		for(int i=1;i<=3;++i)scanf("%lf%lf",&Camera[i].x,&Camera[i].y);
		std::vector<Point> Shadow[4];
		std::vector<Line> Ls;
		for(int i=1;i<=3;++i)
		{
			for(int j=1;j<=n;++j)Shadow[i].push_back(Projection(Camera[i],Mac[j]));//投影到地面
			Shadow[i]=Convex_Hull(Shadow[i]);//求出凸包
			int Ss=Shadow[i].size();
			for(int j=0;j<Ss;++j)Ls.push_back((Line){Shadow[i][(j+1)%Ss],Shadow[i][j]-Shadow[i][(j+1)%Ss]});//转化位半平面交问题
		}
		Shadow[0]=HPI(Ls);
		printf("%.2f\n",Abs(Area(Shadow[0])));//面积取绝对值
	}
	return 0;
}

推荐阅读