POJ - 3335 Rotating Scoreboard （半平面交模板）

链接：https://cn.vjudge.net/problem/POJ-3335

题意：判断直线的半平面交是否有核。（也是判断一个不规则多边形内部是否存在一个区域，可以看到多边形的全貌。）

思路：半平面交板子题，这里存个模板，都是存的边，最后求交点。个人倾向于第一个板子，更易理解些。

1.

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const double eps = 1e-5;
const int N = 2e4+10; 
const double maxx=1e4;
int sgn(double x)
{
	if(fabs(x)<eps) return 0;
	else if(x<0) return -1;
	else return 1;
}
struct Point
{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	Point operator -(const Point& b)const//相减 
	{
		return Point(x-b.x,y-b.y);
	}
	double operator ^(const Point& b)const//叉乘 
	{
		return x*b.y-y*b.x;
	}
	double operator *(const Point& b)const//点乘 
	{
		return x*b.x+y*b.y;
	}
};
struct Line
{
	Point s,e;
	double A;
	Line(){}
	Line(Point ss,Point ee)
	{
		s=ss,e=ee;
	}
	void getangle()
	{
		A=atan2(e.y-s.y,e.x-s.x);
	}
	pair<Point,int> operator &(const Line& b)const//两直线相对关系 
	{
		Point res=s;
		if(sgn((s-e)^(b.s-b.e))==0)
		{
			if(sgn((b.s-s)^(b.e-s))==0)//两直线重合 
				return make_pair(res,0);
			else return make_pair(res,1);//两直线平行 
		}
		double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
		res.x+=(e.x-s.x)*t;
		res.y+=(e.y-s.y)*t;
		return make_pair(res,2);//两直线相交 
	}
};
Point ps[N];
Line ls[N],q[N];
double x;
int n;
double dis(Point a,Point b)
{
	return sqrt((a-b)*(a-b));
}
//注意，这样并不能把点按照逆时针排序 
/*
bool cmp(const Point& a,const Point& b)
{
	x=(a-ps[0])^(b-ps[0]);
	if(sgn(x)==0)
		return dis(ps[0],a)<dis(ps[0],b);
	else if(x>0) return 1;
	else return 0;
}
void anticlock()
{
	int pos=0;
	for(int i=1;i<n;i++)
		if(ps[i].y<ps[pos].y||(ps[i].y==ps[pos].y&&ps[i].x<ps[pos].x))
			pos=i;
	swap(ps[0],ps[pos]);
	sort(ps+1,ps+n,cmp);		
}
*/
//按极角排序，相同时，靠左(或靠下)的在前面 
bool hpicmp(Line a,Line b)
{
	if(sgn(a.A-b.A)==0)	
		return sgn((a.s-b.s)^(b.e-b.s))<=0;		
	else return a.A<b.A;
}
//判断l1与l2的交点是否在l3的右侧 
bool onright(Line l1,Line l2,Line l3)
{
	Point p=(l1&l2).first;
	x=((l3.e-l3.s)^(p-l3.s));
	if(sgn(x)<0) return 1;
	else return 0;
}
//半平面交求核 
bool hpi()
{
	int he=0,ta=1,cnt=0;
    sort(ls,ls+n,hpicmp);
    //去重，只保留极角互不相同的直线 
	cnt=1;
    for(int i = 1;i < n;i++)
        if(sgn(ls[i].A-ls[i-1].A)>0)
        	ls[cnt++]=ls[i];
	//将前两条直线放进队列		 
    q[0]=ls[0];
    q[1]=ls[1];
	for(int i=2;i<cnt;i++)
	{ 
		//说是判断共线，我觉得没必要 
		/*
		if(he<ta&&sgn((q[ta].e-q[ta].s)^(q[ta-1].e-q[ta-1].s))==0
		||sgn((q[he].e-q[he].s)^(q[he+1].e-q[he+1].s))==0)
			return 0;
		*/
		while(he<ta&&onright(q[ta-1],q[ta],ls[i])) ta--;
		while(he<ta&&onright(q[he],q[he+1],ls[i])) he++;
		q[++ta]=ls[i];
	}
	while(he<ta&&onright(q[ta-1],q[ta],q[he])) ta--;
	while(he<ta&&onright(q[he],q[he+1],q[ta-1])) he++;
	if(ta-he+1<=2) return 0;
	else return 1;
}
bool anticlock() 
{
	double ans=0;
	for(int i=1;i<n-1;i++) 
		ans+=((ps[i]-ps[0])^(ps[i+1]-ps[0]));
	return ans<0;
}
int main(void)
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&ps[i].x,&ps[i].y);
		//判断是否为逆时针	
	    if(anticlock()) 
		{
		    for(int i=0;i<n;i++) 
		    {
		        ls[i]=Line(ps[(i+1)%n],ps[i]);
		    	ls[i].getangle(); 
			} 
		} 
		else 
		{
		    for(int i=0;i<n;i++) 
		    {
		      	ls[i]=Line(ps[i],ps[(i+1)%n]);
		      	ls[i].getangle();
			}  
	    }		
		if(hpi())
			puts("YES");
		else puts("NO");
	}
	return 0;
}

2.

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const double eps = 1e-5;
const int N = 1e2+10; 
int sgn(double x)
{
	if(fabs(x)<eps) return 0;
	else if(x<0) return -1;
	else return 1;
}
 
struct Point
{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	Point operator -(const Point& b)const//相减 
	{
		return Point(x-b.x,y-b.y);
	}
	double operator ^(const Point& b)const//叉乘 
	{
		return x*b.y-y*b.x;
	}
	double operator *(const Point& b)const//点乘 
	{
		return x*b.x+y*b.y;
	}
};
struct Line
{
	Point s,e;
	Line(){}
	Line(Point ss,Point ee)
	{
		s=ss,e=ee;
	}
	pair<Point,int> operator &(const Line& b)const//两直线相对关系 
	{
		Point res=s;
		if(sgn((s-e)^(b.s-b.e))==0)
		{
			if(sgn((b.s-s)^(b.e-s))==0)//两直线重合 
				return make_pair(res,0);
			else return make_pair(res,1);//两直线平行 
		}
		double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
		res.x+=(e.x-s.x)*t;
		res.y+=(e.y-s.y)*t;
		return make_pair(res,2);//两直线相交 
	}
};
Point ps[N];
Line ls[N],q[N];
double x;
int n;
double dis(Point a,Point b)
{
	return sqrt((a-b)*(a-b));
}
//注意，这样并不能把点按照逆时针排序 
/*
bool cmp(const Point& a,const Point& b)
{
	x=(a-ps[0])^(b-ps[0]);
	if(sgn(x)==0)
		return dis(ps[0],a)<dis(ps[0],b);
	else if(x>0) return 1;
	else return 0;
}
void anticlock()
{
	int pos=0;
	for(int i=1;i<n;i++)
		if(ps[i].y<ps[pos].y||(ps[i].y==ps[pos].y&&ps[i].x<ps[pos].x))
			pos=i;
	swap(ps[0],ps[pos]);
	sort(ps+1,ps+n,cmp);		
}
*/
//获得极角 
double getA(Line a)
{
	return atan2(a.e.y-a.s.y,a.e.x-a.s.x);
}
//当极角相同时,最靠左的在后面 
bool hpicmp(Line a,Line b)
{
	double A=getA(a),B=getA(b);
	if(sgn(A-B)==0)	
		return ((a.e-a.s)^(b.e-a.s))>=0;
	else return A<B;
}
//判断l1与l2的交点是否在l3右边 
bool onright(Line l1,Line l2,Line l3)
{
	Point p=(l1&l2).first;
	x=((l3.e-l3.s)^(p-l3.s));
	if(sgn(x)<0) return 1;
	else return 0;
}
//半平面交 
bool hpi()
{
	int he=0,ta=0,cnt=0;
	//按极角排序 
	sort(ls,ls+n,hpicmp);
	//去重   
	for(int i=0;i<n-1;i++)
	{
		if(sgn(getA(ls[i])-getA(ls[i+1]))==0)
			continue;
		ls[cnt++]=ls[i];
	}
	ls[cnt++]=ls[n-1];
	//求半平面交 
	for(int i=0;i<cnt;i++)
	{
		while(ta-he>1&&onright(q[ta-2],q[ta-1],ls[i])) ta--;
		while(ta-he>1&&onright(q[he],q[he+1],ls[i])) he++;
		q[ta++]=ls[i];
	}
	while(ta-he>1&&onright(q[ta-2],q[ta-1],q[he])) ta--;
	while(ta-he>1&&onright(q[he],q[he+1],q[ta-1])) he++;
	if(ta-he>2) return 1;
	else return 0;  
}
bool judge() 
{
	double ans=0;
	for (int i=1;i<n-1;i++) 
		ans+=((ps[i]-ps[0])^(ps[i+1]-ps[0]));
	return ans<0;
}
int main(void)
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&ps[i].x,&ps[i].y);
	    if(judge()) 
		{
			for (int i=0;i<n;i++) 
				ls[i]=Line(ps[(i+1)%n],ps[i]);
	    } 
		else 
		{
			for (int i=0;i<n;i++) 
				ls[i]=Line(ps[i],ps[(i+1)%n]);
	    }		
		if(hpi())
			puts("YES");
		else puts("NO");
	}
	
	return 0;
}