题解

直线的交
凸多边形的判定
点在多边形内的判定
线段在多边形内的判定
多边形的重心

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
const int N = 1e3+5;
const int offset = 1e8;
const db eps = 1e-8; 

struct point{
	db x,y;
	point(db _x=0,db _y=0){
		x=_x;y=_y;
	} 
};
struct line{
	point a,b;
	line(point _a=point(0,0),point _b=point(0,0)){
		a=_b;b=_b;
	} 
};

//p0->p1与p0->p2的叉积 
double xmult(point p1,point p2,point p0){
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

//直线的交点 
point intersection(line u,line v){
	point ret=u.a;
	double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
			/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
	ret.x+=(u.b.x-u.a.x)*t;
	ret.y+=(u.b.y-u.a.y)*t;
	return ret;
}

//判定是否为凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线
int is_convex(int n,point* p){
	int s[3]={1,1,1};
	for(int i=0;i<n;++i)s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
	return s[1]|s[2];
}
 
//判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回2
int inside_convex(point q,int n,point* p){
	int s[3]={1,1,1};
	for(int i=0;i<n;++i)s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
	if(!s[0])return 2;
	return s[1]|s[2];
}

//判断点a,b是否在直线l的两侧
int opposite_side(point p1,point p2,line l){
	return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps;
}

//判断点是否在线段上
inline int dot_online_in(point p,point l1,point l2){
	return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}
 
//判定点是否在任意多边形内,顶点按顺时针或逆时针给出
//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限
int inside_polygon(point q,int n,point* p,int on_edge=1){
	point q2;
	int i=0,count;
	while(i<n){
		for(count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;++i)
		if(dot_online_in(q,p[i],p[(i+1)%n]))return on_edge;
		else if(zero(xmult(q,q2,p[i])))break;
		else if(opposite_side(p[i],p[(i+1)%n],line(q,q2))&&opposite_side(q,q2,line(p[i],p[(i+1)%n])))count++;
	}
	return count&1;
}
 
//判定线段是否在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
int inside_polygon(point l1,point l2,int n,point* p){
	point t[N],tt;
	int k=0;
	if(!inside_polygon(l1,n,p)||!inside_polygon(l2,n,p))return 0;
	for(int i=0;i<n;++i){
		if(opposite_side(l1,l2,line(p[i],p[(i+1)%n]))&&opposite_side(p[i],p[(i+1)%n],line(l1,l2)))return 0;
		else if(dot_online_in(l1,p[i],p[(i+1)%n]))t[k++]=l1;
		else if(dot_online_in(l2,p[i],p[(i+1)%n]))t[k++]=l2;
		else if(dot_online_in(p[i],l1,l2))t[k++]=p[i];
	}
	for(int i=0;i<k;i++)
	for(int j=i+1;j<k;j++){
		tt.x=(t[i].x+t[j].x)/2;
		tt.y=(t[i].y+t[j].y)/2;
		if(!inside_polygon(tt,n,p))return 0;
	}
	return 1;
}

//三点重心 
point barycenter(point a,point b,point c){
	line u,v;
	u.a.x=(a.x+b.x)/2;
	u.a.y=(a.y+b.y)/2;
	u.b=c;
	v.a.x=(a.x+c.x)/2;
	v.a.y=(a.y+c.y)/2;
	v.b=b;
	return intersection(u,v);
}

//多边形重心
point barycenter(int n,point* p){
	point ret,t;
	db t1=0,t2;
	ret.x=ret.y=0;
	for(int i=1;i<n-1;++i)
	if(fabs(t2=xmult(p[0],p[i],p[i+1]))>eps){
		t=barycenter(p[0],p[i],p[i+1]);
		ret.x+=t.x*t2;
		ret.y+=t.y*t2;
		t1+=t2;
	}
	if(fabs(t1)>eps)ret.x/=t1,ret.y/=t1;
	return ret;
}