Written by daweibayu
on July 29, 2017

Poj 1269

Intersecting Lines 简而言之就是求两条线的关系，平行？重合？相交？如果相交的话求出交叉点。方式有很多种，有用向量的，有用斜率的。其实这算是个水题，只不过需要考虑点边界情况。

代码如下：

#include <math.h>
#include <stdio.h>

struct Point {
    double x;
    double y;
    
    bool operator==(const Point &other) const {
        return (x == other.x && y == other.y);
    }
};

/**
 * 假设直线方程为 y = kx + n
 **/
struct Line {
    struct Point a;
    struct Point b;
    
    bool isVertical() {
        return a.x == b.x;
    }
    
    // 这里需要注意直线情况
    double getSlope() {
        return (b.y - a.y)/(b.x - a.x);
    }
    
    double getSuffix() {
        return a.y - getSlope()*a.x;
    }
};

/**
 * 是否平行
 **/
bool isParallel(struct Line line1, struct Line line2) {
    double dxLine1 = line1.a.x - line1.b.x;
    double dyline1 = line1.a.y - line1.b.y;
    
    double dxLine2 = line2.a.x - line2.b.x;
    double dyline2 = line2.a.y - line2.b.y;
    
    if (0 == dxLine1) {
        return (0 == dxLine2);
    }
    
    return (dyline2*dxLine1 == dyline1*dxLine2);
}

/**
 * 是否是同一条直线
 **/
bool isInLine(struct Line line1, struct Line line2) {
    
    // 先计算是否平行，不平行的线一定不会是同一条直线
    if(!isParallel(line1, line2)) {
        return false;
    }
    
    // 平行且过同一个点，则肯定是同一条直线
    if (line1.a == line2.a) {
        return true;
    }
    
    // 否则以 line1.a line2.a 构造第三条线，看是否与 line1 平行
    struct Line lineTmp = {line1.a, line2.a};
    return isParallel(line1, lineTmp);
}

struct Point intersectPoint(struct Line line1, struct Line line2) {
    struct Point point = {0, 0};
    if (line1.isVertical()) {
        point.x = line1.a.x;
        point.y = line2.getSlope()*point.x + line2.getSuffix();
    } else if (line2.isVertical()) {
        point.x = line2.a.x;
        point.y = line1.getSlope()*point.x + line1.getSuffix();
    } else {
        point.x = (line2.getSuffix() - line1.getSuffix())/(line1.getSlope() - line2.getSlope());
        point.y = line1.getSlope()*point.x + line1.getSuffix();
    }
    return point;
}

int main(int argc, const char * argv[]) {
    
    int turn = 0;
    scanf("%d", &turn);
    
    printf("INTERSECTING LINES OUTPUT\n");
    
    for (int i = 0; i < turn; i++) {
        struct Line line1, line2;
        scanf("%lf %lf %lf %lf", &line1.a.x, &line1.a.y, &line1.b.x, &line1.b.y);
        scanf("%lf %lf %lf %lf", &line2.a.x, &line2.a.y, &line2.b.x, &line2.b.y);
        
        if (isInLine(line1, line2)) {
            printf("LINE\n");
            continue;
        }
        
        if (isParallel(line1, line2)) {
            printf("NONE\n");
            continue;
        }
        
        struct Point point = intersectPoint(line1, line2);
        printf("POINT %.2lf %.2lf\n", point.x, point.y);
    }
    printf("END OF OUTPUT");
}

← → Top