|
|
| （未显示同一用户的4个中间版本） |
| 第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>
| |
| | |
| 实际上有三维上的意义，但是信息学竞赛中一般只关注上面式子的值。
| |
| | |
| 意义：
| |
| * 结果的绝对值恰好为两向量为邻边的平行四边形的面积，因此可以用来计算三角形面积。
| |
| * 可以利用正负值判断两个向量的位置关系。
| |
| {{bc|lang=cpp|code=
| |
| // 传入两个点，返回对应向量（第一个点指向第二个点）
| |
| 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;
| |
| }
| |
| }}
| |
| | |
| ==线段相交判断==
| |
| | |
| 对于四个点 <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> 的两边。
| |
| | |
| 显然如果两个条件都满足，那么两线段相交。
| |
| | |
| {{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 <nowiki>||</nowiki> 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;
| |
| }
| |
| }}
| |