FZU 2273 Triangles(计算几何)

文章地址:http://henuly.top/?p=860

Description:

This is a simple problem. Given two triangles A and B, you should determine they are intersect, contain or disjoint. (Public edge or point are treated as intersect.)

Input:

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6. All the coordinate are integer. (X1,Y1) , (X2,Y2), (X3,Y3) forms triangles A ; (X4,Y4) , (X5,Y5), (X6,Y6) forms triangles B.

-10000<=All the coordinate <=10000

Output:

For each test case, output “intersect”, “contain” or “disjoint”.

Sample Input:

2
0 0 0 1 1 0 10 10 9 9 9 10
0 0 1 1 1 0 0 0 1 1 0 1

Sample Output:

disjoint
intersect

题目链接

给出两个三角形分别三个顶点的坐标位置判断两个三角的位置关系(相交、相离、包含)。

1. 判断两三角形是否有相交的边，若有则可能的位置关系为包含或者相交
2. 判断一个三角形顶点(三个)是否在另一三角形内部，若全在则位置关系为包含，若全不在则为相离，若不全在则相交

判断边是否相交的方式:叉乘

判断一点是否在三角形内部的方式:枚举三角形三个顶点，做此顶点上两条边的射线，连接判断点与顶点，通过叉乘判断此线段是否在两射线之间，若对于三个顶点都满足则此判断点在三角形内部，否则不在。

AC代码:

#include <cstdio>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
    double X, Y;
    Point(double _X = 0, double _Y = 0): X(_X), Y(_Y) {}
    void Input() {
        scanf("%lf%lf", &X, &Y);
    }
    Point operator - (const Point &b) const {
        return Point (X - b.X, Y - b.Y);
    }
    double operator ^ (const Point &b) const {
        return X * b.Y - Y * b.X;
    }
    bool operator == (const Point &b) const {
        return fabs(X - b.X) < eps && fabs(Y - b.Y) < eps;
    }
};

struct Segment {
    Point P, Q;
    void Input() {
        P.Input(); Q.Input();
    }
    double operator ^ (const Segment &b) const {
        return (Q - P) ^ (b.Q - b.P);
    }
};

bool IntersectJudge(Segment A, Segment B) {
    // 对于这个OJ的编译器不能使用"Segment{X, Y};"
    Segment Temp1, Temp2, Temp3, Temp4;
    Temp1.P = A.P; Temp1.Q = B.P;
    Temp2.P = A.P; Temp2.Q = B.Q;
    Temp3.P = B.P; Temp3.Q = A.P;
    Temp4.P = B.P; Temp4.Q = A.Q;
    if ((A ^ Temp1) * (A ^ Temp2) <= 0 && (B ^ Temp3) * (B ^ Temp4) <= 0) {
        return true;
    }
    return false;
}

bool ContainJudge(Segment A, Segment B, Point C) {
    Point Vertex;
    if (A.P == B.P || A.P == B.Q) {
        Vertex = A.P;
        if (A.P == B.Q) {
            Point Temp = B.P;
            B.P = B.Q;
            B.Q = Temp;
        }
    }
    else if (A.Q == B.P || A.Q == B.Q) {
        Vertex = A.Q;
        if (A.Q == B.P) {
            Point Temp = B.Q;
            B.Q = B.P;
            B.P = Temp;
        }
    }
    Segment Judge;
    Judge.P = Vertex; Judge.Q = C;
    if ((A ^ Judge) * (B ^ Judge) <= 0) {
        return true;
    }
    return false;
}

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        Segment Temp;
        int nx[3] = {0, 0, 1}, ny[3] = {1, 2, 2};
        Segment TriangleA[3], TriangleB[3];
        Point Vertex[6];
        for (int i = 0; i < 6; ++i) {
            Vertex[i].Input();
        }
        for (int i = 0; i < 3; ++i) {
            TriangleA[i].P = Vertex[nx[i]]; TriangleA[i].Q = Vertex[ny[i]];
        }
        for (int i = 0; i < 3; ++i) {
            TriangleB[i].P = Vertex[nx[i] + 3]; TriangleB[i].Q = Vertex[ny[i] + 3];
        }
        bool IntersectFlag = false;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (IntersectJudge(TriangleA[i], TriangleB[j])) {
                    IntersectFlag = true;
                }
            }
        }
        bool ContainFlag = true;;
        for (int i = 0; i < 3; ++i) {
            for (int j = 3; j < 6; ++j) {
                if (!ContainJudge(TriangleA[nx[i]], TriangleA[ny[i]], Vertex[j])) {
                    ContainFlag = false;
                }
            }
        }
        if (ContainFlag) {
            printf("contain\n");
            continue;
        }
        ContainFlag = true;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (!ContainJudge(TriangleB[nx[i]], TriangleB[ny[i]], Vertex[j])) {
                    ContainFlag = false;
                }
            }
        }
        if (ContainFlag) {
            printf("contain\n");
            continue;
        }
        if (IntersectFlag) {
            printf("intersect\n");
            continue;
        }
        printf("disjoint\n");
    }
    return 0;
}