FZU-2273 Triangles (判断两个三角形相离、相交、包含)

题意

给出两个三角形各顶点在直角坐标系上的坐标，问这两个三角形的位置关系是相离、相交还是包含？(共边或共点算相交)

思路

先判断是否相交（因为共边和共点算相交，先判断相交会方便一些），再判断是否包含，两种都不是则为相离。

判断三角形相交

两个三角形各拿出一条边，共有9种组合，判断每种组合的两条边是否相交，出现一对边相交则两个三角形相交，问题转换为如何判断线段相交。

考虑向量叉积，首先要知道一个定理，若$\overrightarrow {a}\times \overrightarrow {b}$的结果小于0，表示$\overrightarrow {b}$在$\overrightarrow {a}$的顺时针方向；若结果大于0，表示$\overrightarrow {b}$在$\overrightarrow {a}$的逆时针方向；若结果等于0，说明$\overrightarrow {a}$和$\overrightarrow {b}$平行。（顺逆时针是指两向量平移至起点相连，从某个方向旋转到另一个向量小于180度）

线段AB与线段CD相交的充要条件是直线AB与线段CD相交，并且直线CD与线段AB相交。判断直线AB与线段CD相交只需要判断C、D两点分别在直线AB的两边，即$\overrightarrow{AB}\times \overrightarrow{AC}$与$\overrightarrow{AB}\times \overrightarrow{AD}$异号，判断直线CD与线段AB相交同理。

判断三角形包含

$\Delta ABC$被$\Delta DEF$包含的充要条件是A、B、C三个点都在$\Delta DEF$内部。一个点$X$在$\Delta DEF$内部的充要条件是$S_{\Delta DEF}=S_{\Delta DEX}+S_{\Delta DFX}+S_{\Delta EFX}$。计算三角形面积可用向量叉积，$S_{\Delta ABC}=|\overrightarrow{AB}\times \overrightarrow{AC}|/2$。

代码实现

#include <cstdio>
#include <cmath>
const double eps = 1e-8;
struct Point
{
    double x, y;
} P[2][4];
double xmult(Point a, Point b, Point c) { // 向量ab与向量ac的叉积
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                scanf("%lf %lf", &P[i][j].x, &P[i][j].y);
            }
        }
        P[0][3] = P[0][0], P[1][3] = P[1][0];
        bool ints = false;
        for (int i = 0; i < 3 && !ints; i++) {
            for (int j = 0; j < 3 && !ints; j++) {
                // 第0个三角形的第i条边与第1个三角形的第j条边是否相交
                if (xmult(P[0][i], P[0][i+1], P[1][j]) * xmult(P[0][i], P[0][i+1], P[1][j+1]) < eps &&
                    xmult(P[1][j], P[1][j+1], P[0][i]) * xmult(P[1][j], P[1][j+1], P[0][i+1]) < eps) {
                    ints = true;
                }
            }
        }
        if (ints) {
            puts("intersect");
            continue;
        }
        bool in = false;
        for (int i = 0; i < 2; i++) {
            double area = fabs(xmult(P[i][0], P[i][1], P[i][2]));
            for (int j = 0; j < 3; j++) {
                double area2 = 0;
                for (int k = 0; k < 3; k++) {
                    area2 += fabs(xmult(P[i^1][j], P[i][k], P[i][k+1]));
                }
                // 三角形i^1的第j个点是否在三角形i里面
                if (fabs(area - area2) < eps) in = true;
                else {
                    in = false;
                    break;
                }
            }
            if (in) break;
        }
        if (in) puts("contain");
        else puts("disjoint");
    }
    return 0;
}

View Code