计算几何 - 版本历史

33DAI：批量导入三三文档

2026-05-20T18:24:19Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第1行：		第1行：
	~~==欧几里得距离==~~		#REDIRECT [[06-数学相关/06-计算几何]]
			[[Category:三三文档]]
	* <math>(x_1,y_1)</math> 与 <math>(x_2,y_2)</math> 的距离为 <math>\sqrt{(x_1-x_2)^2+(y_1-~~y_2)^2}</math>~~
	* <math>(x_1,y_1,z_1)</math> 与 <math>(x_2,y_2,z_2)</math> 的距离为 <math>\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}</math>

	~~==海伦公式==~~

	~~三角形三边长分别为 <math>a,b,c</math>，那么定义半周长 <math>p=\frac{a+b+c}{2}<~~/~~math>~~

	~~则三角形面积为 <math>\sqrt{p(p-a)(p-b)(p~~-~~c)}</math>~~

	~~==向量叉乘==~~

	~~<math>~~
	~~\vec{a}=(a_x,a_y),\ \vec{b}=(b_x,b_y)~~
	~~\quad\Rightarrow\quad~~
	~~\vec{a} \times \vec{b} = a_x b_y - a_y b_x~~
	~~</math>~~

	~~实际上有三维上的意义，但是信息学竞赛中一般只关注上面式子的值。~~

	~~意义：~~
	* 结果的绝对值恰好为两向量为邻边的平行四边形的面积，因此可以用来计算三角形面积。
	* 可以利用正负值判断两个向量的位置关系。

	~~<syntaxhighlight lang="cpp" line>~~

	~~// 传入两个点，返回对应向量（第一个点指向第二个点）~~
	~~pair<double, double> getV(pair<double, double> a, pair<double, double> b)~~
	{
	~~return {b.first - a.first, b.second - a.second};~~
	}
	~~// 传入两个向量，返回叉乘结果~~
	~~// 如果结果为正，第二个向量偏左，否则偏右~~
	~~double getMul(pair<double, double> a, pair<double, double> b)~~
	{
	~~return a.first * b.second - a.second * b.first;~~
	}
	~~</syntaxhighlight>~~

	~~==线段相交判断==~~

	~~对于四个点 <math>A,B,C,D</math>，判断线段 <math>AB</math> 与线段 <math>CD</math> 是否相交。~~

	~~通过计算 <math>\vec{AB}\times \vec{AC}</math> 与 <math>\vec{AB}\times \vec{AD}</math>，如果结果一正一负，则 <math>C,D</math> 两点处于直线 <math>AB</math> 的两边。~~

	~~同理可以判断<math>A,B</math> 两点是否处于直线 <math>CD</math> 的两边。~~

	~~显然如果两个条件都满足，那么两线段相交。~~

	~~<syntaxhighlight lang="cpp" line>~~
	~~// 判断两个线段是否相交（ab ~ cd）~~
	~~bool checkX(pair<double, double> a, pair<double, double> b,~~
	~~pair<double, double> c, pair<double, double> d)~~
	{
	~~double x, y;~~
	~~// c,d 是否在直线 ab 的两边~~
	~~pair<double, double> AB = getV(a, b);~~
	~~pair<double, double> AC = getV(a, c);~~
	~~pair<double, double> AD = getV(a, d);~~
	~~x = getMul(AB, AC);~~
	~~y = getMul(AB, AD);~~
	~~if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧~~
	~~return false;~~
	~~// a,b 是否在直线 cd 的两边~~
	~~pair<double, double> CD = getV(c, d);~~
	~~pair<double, double> CA = getV(c, a);~~
	~~pair<double, double> CB = getV(c, b);~~
	~~x = getMul(CD, CA);~~
	~~y = getMul(CD, CB);~~
	~~if (x * y > 0)~~
	~~return false;~~
	~~return true;~~
	}
	~~</syntaxhighlight>~~

2026年2月12日 (四) 03:56 33DAI

2026-02-12T03:56:31Z

←上一版本		2026年2月12日 (四) 03:56的版本
第24行：		第24行：
	* 可以利用正负值判断两个向量的位置关系。		* 可以利用正负值判断两个向量的位置关系。

	<~~pre~~>		<syntaxhighlight lang="cpp" line>

	// 传入两个点，返回对应向量（第一个点指向第二个点）		// 传入两个点，返回对应向量（第一个点指向第二个点）
	pair<double, double> getV(pair<double, double> a, pair<double, double> b)		pair<double, double> getV(pair<double, double> a, pair<double, double> b)
第36行：		第37行：
	return a.first * b.second - a.second * b.first;		return a.first * b.second - a.second * b.first;
	}		}
	</~~pre~~>		</syntaxhighlight>

	==线段相交判断==		==线段相交判断==
第48行：		第49行：
	显然如果两个条件都满足，那么两线段相交。		显然如果两个条件都满足，那么两线段相交。

	<~~pre~~>		<syntaxhighlight lang="cpp" line>
	// 判断两个线段是否相交（ab ~ cd）		// 判断两个线段是否相交（ab ~ cd）
	bool checkX(pair<double, double> a, pair<double, double> b,		bool checkX(pair<double, double> a, pair<double, double> b,
第72行：		第73行：
	return true;		return true;
	}		}
	</~~pre~~>		</syntaxhighlight>

2026年2月12日 (四) 02:57 33DAI

2026-02-12T02:57:32Z

←上一版本		2026年2月12日 (四) 02:57的版本
第23行：		第23行：
	* 结果的绝对值恰好为两向量为邻边的平行四边形的面积，因此可以用来计算三角形面积。		* 结果的绝对值恰好为两向量为邻边的平行四边形的面积，因此可以用来计算三角形面积。
	* 可以利用正负值判断两个向量的位置关系。		* 可以利用正负值判断两个向量的位置关系。
	~~{{bc\|lang=cpp\|code=~~
			<pre>
	// 传入两个点，返回对应向量（第一个点指向第二个点）		// 传入两个点，返回对应向量（第一个点指向第二个点）
	pair<double, double> getV(pair<double, double> a, pair<double, double> b)		pair<double, double> getV(pair<double, double> a, pair<double, double> b)
第35行：		第36行：
	return a.first * b.second - a.second * b.first;		return a.first * b.second - a.second * b.first;
	}		}
	}}		</pre>

	==线段相交判断==		==线段相交判断==

33DAI：/* 线段相交判断 */

2026-02-12T02:47:53Z

线段相交判断

←上一版本		2026年2月12日 (四) 02:47的版本
第47行：		第47行：
	显然如果两个条件都满足，那么两线段相交。		显然如果两个条件都满足，那么两线段相交。

	~~{{bc\|lang=cpp\|code=~~		<pre>
	// 判断两个线段是否相交（ab ~ cd）		// 判断两个线段是否相交（ab ~ cd）
	bool checkX(pair<double, double> a, pair<double, double> b,		bool checkX(pair<double, double> a, pair<double, double> b,
第71行：		第71行：
	return true;		return true;
	}		}
	}}		</pre>

33DAI：/* 线段相交判断 */

2026-02-12T02:11:07Z

线段相交判断

←上一版本		2026年2月12日 (四) 02:11的版本
第59行：		第59行：
	x = getMul(AB, AC);		x = getMul(AB, AC);
	y = getMul(AB, AD);		y = getMul(AB, AD);
	if (x > 0 && y > 0 ~~<nowiki>~~\|\|~~</nowiki>~~ x < 0 && y < 0) // c,d 在 ab 同一侧		if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧
	return false;		return false;
	// a,b 是否在直线 cd 的两边		// a,b 是否在直线 cd 的两边

33DAI：/* 线段相交判断 */

2026-02-12T01:51:57Z

线段相交判断

←上一版本		2026年2月12日 (四) 01:51的版本
第65行：		第65行：
	pair<double, double> CA = getV(c, a);		pair<double, double> CA = getV(c, a);
	pair<double, double> CB = getV(c, b);		pair<double, double> CB = getV(c, b);
	x = getMul(AB, AC);		x = getMul(CD, CA);
	y = getMul(AB, AD);		y = getMul(CD, CB);
	if (x * y > 0)		if (x * y > 0)
	return false;		return false;

33DAI：/* 线段相交判断 */

2026-02-12T01:49:22Z

线段相交判断

←上一版本		2026年2月12日 (四) 01:49的版本
第59行：		第59行：
	x = getMul(AB, AC);		x = getMul(AB, AC);
	y = getMul(AB, AD);		y = getMul(AB, AD);
	if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧		if (x > 0 && y > 0 <nowiki>\|\|</nowiki> x < 0 && y < 0) // c,d 在 ab 同一侧
	return false;		return false;
	// a,b 是否在直线 cd 的两边		// a,b 是否在直线 cd 的两边

33DAI：/* 线段相交判断 */

2026-02-12T01:48:28Z

线段相交判断

←上一版本		2026年2月12日 (四) 01:48的版本
第59行：		第59行：
	x = getMul(AB, AC);		x = getMul(AB, AC);
	y = getMul(AB, AD);		y = getMul(AB, AD);
	if (x > 0 && y > 0 ~~<nowiki>~~\|\|~~</nowiki>~~ x < 0 && y < 0) // c,d 在 ab 同一侧		if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧
	return false;		return false;
	// a,b 是否在直线 cd 的两边		// a,b 是否在直线 cd 的两边

33DAI：/* 线段相交判断 */

2026-02-12T01:38:43Z

线段相交判断

←上一版本		2026年2月12日 (四) 01:38的版本
第59行：		第59行：
	x = getMul(AB, AC);		x = getMul(AB, AC);
	y = getMul(AB, AD);		y = getMul(AB, AD);
	if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧		if (x > 0 && y > 0 <nowiki>\|\|</nowiki> x < 0 && y < 0) // c,d 在 ab 同一侧
	return false;		return false;
	// a,b 是否在直线 cd 的两边		// a,b 是否在直线 cd 的两边

33DAI：/* 线段相交判断 */

2026-02-12T01:35:05Z

线段相交判断

←上一版本		2026年2月12日 (四) 01:35的版本
第46行：		第46行：

	显然如果两个条件都满足，那么两线段相交。		显然如果两个条件都满足，那么两线段相交。

			{{bc\|lang=cpp\|code=
			// 判断两个线段是否相交（ab ~ cd）
			bool checkX(pair<double, double> a, pair<double, double> b,
			pair<double, double> c, pair<double, double> d)
			{
			double x, y;
			// c,d 是否在直线 ab 的两边
			pair<double, double> AB = getV(a, b);
			pair<double, double> AC = getV(a, c);
			pair<double, double> AD = getV(a, d);
			x = getMul(AB, AC);
			y = getMul(AB, AD);
			if (x > 0 && y > 0 \|\| x < 0 && y < 0) // c,d 在 ab 同一侧
			return false;
			// a,b 是否在直线 cd 的两边
			pair<double, double> CD = getV(c, d);
			pair<double, double> CA = getV(c, a);
			pair<double, double> CB = getV(c, b);
			x = getMul(AB, AC);
			y = getMul(AB, AD);
			if (x * y > 0)
			return false;
			return true;
			}
			}}

计算几何 - 版本历史

33DAI：​批量导入三三文档

2026年2月12日 (四) 03:56 33DAI

2026年2月12日 (四) 02:57 33DAI

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：​/* 线段相交判断 */

33DAI：批量导入三三文档

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */

33DAI：/* 线段相交判断 */