计算几何基础

标签（空格分隔）：计算几何

三角函数、平面向量

判断线段相交

如果判断两条线段是否是规范相交（恰有一个不是端点的公共点），做跨立实验即可。比如对于$p_1,p_2$所组成的线段与$p_3,p_4$所组成的线段，判断$p_1,p_2$是否在直线$p_3,p_4$的异侧，再判断$p_3,p_4$是否在直线$p_1,p_2$的异侧。

bool Online(Point a[],Point b[])
{
	if(dump(Cross(a[0]-b[0],b[1]-b[0]))*dump(Cross(a[1]-b[0],b[1]-b[0]))>=0) return 0;
	if(dump(Cross(b[0]-a[0],a[1]-a[0]))*dump(Cross(b[1]-a[0],a[1]-a[0]))>=0) return 0;
	return 1;
}

如果要让作为公共部分也返回 1 ，那么就必须特判，直接将大于等于改成大于是错误的写法，因为有可能在做第一个跨立实验时，叉乘选择的起始点恰好是那个在直线$p_2,p_3$上但却不在线段$p_2,p_3$上的点。

bool Onseg(Point r,Point l,Point a)
{
	if(a.x<min(l.x,r.x)||a.x>max(l.x,r.x)) return 0;
	if(a.y<min(l.y,r.y)||a.y>max(l.y,r.y)) return 0;
	return 1;
}
bool Inter(Point a0,Point a1,Point b0,Point b1)
{
	double d1=dump(Cross(a0-b0,b1-b0)),d2=dump(Cross(a1-b0,b1-b0));
	double d3=dump(Cross(b0-a0,a1-a0)),d4=dump(Cross(b1-a0,a1-a0));
	if(d1*d2<0&&d3*d4<0) return 1;
	if(d1==0&&Onseg(b1,b0,a0)) return 1;
	if(d2==0&&Onseg(b1,b0,a1)) return 1;
	if(d3==0&&Onseg(a1,a0,b0)) return 1;
	if(d4==0&&Onseg(a1,a0,b1)) return 1;
	return 0;
}

计算两条直线的交点

第一条直线经过$p_1,p_2$，第二条直线经过$p_3,p_4$，那么我们可以以三角形$p_1p_2p_3$和三角形$p_1p_2p_4$的有向面积的比值（强调有向是为了避免关于几个点的相对位置的讨论），对$p_3,p_4$的坐标进行放缩，具体如下：

Point get(Point p1,Point p2,Point s1,Point s2)
{
	double t1=Cross(s1-p1,p2-p1),t2=Cross(p2-p1,s2-p1);
	Point p;
	p.x=(s1.x*t2+s2.x*t1)/(t1+t2);
	p.y=(s1.y*t2+s2.y*t1)/(t1+t2);
	return p;
}

注意，在利用类似的思想进行放缩的时候，要格外注意分母是否可能为 0 。

角度相关的数学函数

sin cos tan：传入弧度制的角度，返回对应的函数值
asin acos atan：传入函数值，返回弧度制的角度

特别特别重要的：
atan2(y,x)：如果点$(x,y)$在一二象限，则返回有$x$的正半轴逆时针转到原点与$(y,x)$所连的射线扫过的角的大小（返回值为正）；否则，返回顺时针转到原点与$(y,x)$所连的射线扫过的角，返回值为负。返回值为弧度制，且绝对值小于$\pi$。
利用三角函数得到$\pi$：acos（-1.0）如果写 1 ，使用C++编译器提交的时候可能会CE。

多边形相关

计算多边形面积

任取一个点，这个点与多边形的每一条边组成的三角形的有向面积之和的绝对值等于多边形面积。

判断多边形是否是凸多边形

1.判断每一条边的拐向是否与第一条边的拐向相同。
2.求一遍凸包，判断凸包上是否有$n$个点

判断点是否在多边形内

1.从点出发向左画一条水平的射线，计算射线与多边形的交点次数。对于线段的端点，我们取每一条线段靠下的端点，不取每一条线段靠上的端点（如果是水平的线段，那么我们取左端点，不取右端点）。这相当于是把点向下平移了$eps$的距离。如果次数为奇数，则在多边形内，否则在多边形外。
2.这个点与多边形的每一条边叉乘的结果，先取绝对值再求和，比较得到的值是否等于面积。如果相等，则在多边形内，否则不在。

皮克定理

皮克定理：整点构成的多边形，内部的点数为$I$，边上的点数为$E$，面积为$S$，则$S=I+{E\over 2}-1$