【POJ-1269】Intersecting Lines【直线位置判断】

【POJ-1269】Intersecting Lines【直线位置判断】

问题链接:https://vjudge.net/problem/POJ-1269

Solution:

直线判断比线段判断简单,不过与线段判断不同的是,对于直线来说,平行是最好判断的,判断两个方向向量叉积是否为0就可以判断平行;至于判断共线,从两条直线上各取两点,首先固定选取一条直线上的这两个点,之后在另一条直线上分别取两点分别与刚才取的两点求一下三点的旋转方向,即通过叉积,之后只要确认两组三个点分别都是共线的,就可以确认两条直线共线。剩下的都是相交。

求交点直接使用解析几何的办法就好了,如果使用斜率需要讨论斜率是否存在的情况。

#include <iostream>

using namespace std;

struct Point {
    int x, y;
    Point operator - (Point b) {
        Point ret = {x - b.x, y - b.y};
        return ret;
    }
    bool operator == (const Point &p) {return x == p.x && y == p.y;}
    int cross(Point v) {
        return x * v.y - y * v.x;
    }
};
inline int maxi(int a, int b) {return a > b ? a : b;}
inline int mini(int a, int b) {return a < b ? a : b;}
enum {COUNT, CLOCK, COL};
int getOrientation(Point a, Point b, Point c) {
    Point vab = b - a;      /* The vector of a -> b */
    Point vac = c - a;      /* The vector of a -> c */
    int crossPro = vab.cross(vac);
    if (crossPro < 0) return CLOCK;
    if (crossPro > 0) return COUNT;
    return COL;
}

enum {POINT, NONE, LINE};
int isIntersect(Point ps1, Point pe1, Point ps2, Point pe2) {
    int oa = getOrientation(ps1, ps2, pe1);
    int ob = getOrientation(ps1, pe2, pe1);
    if (oa == COL && ob == COL) return LINE;
    Point v = pe1 - ps1;
    Point v2 = pe2 - ps2;
    if (!v.cross(v2)) return NONE;
    return POINT;
}
double ans[2];
void setAns(const Point &p) {
    ans[0] = p.x;
    ans[1] = p.y;
}
void getInterPoint(Point ps1, Point pe1, Point ps2, Point pe2) {
    if (ps1 == ps2 || ps1 == pe2) setAns(ps1);
    if (pe1 == ps2 || pe1 == pe2) setAns(pe1);
    double k1 = (pe1.y - ps1.y) * 1.0 / (pe1.x - ps1.x);
    double b1 = ps1.y - ps1.x * k1;
    double k2 = (pe2.y - ps2.y) * 1.0 / (pe2.x - ps2.x);
    double b2 = ps2.y - ps2.x * k2;
    if (ps1.x == pe1.x) {
        ans[0] = ps1.x;
        ans[1] = k2 * ans[0] + b2;
    } else if (ps2.x == pe2.x) {
        ans[0] = ps2.x;
        ans[1] = k1 * ans[0] + b1;
    } else {
        ans[0] = (b2 - b1) / (k1 - k2);
        ans[1] = k1 * ans[0] + b1;
    }
}

int main(void) {
    int n;
    Point ps1, pe1, ps2, pe2;
    while (~scanf("%d", &n)) {
        printf("INTERSECTING LINES OUTPUT\n");
        while (n--) {
            scanf("%d%d%d%d%d%d%d%d", &ps1.x, &ps1.y, &pe1.x, &pe1.y,
                &ps2.x, &ps2.y, &pe2.x, &pe2.y);
            if (ps1 == pe1 || ps2 == pe2) {
                printf("NONE\n");
                continue;
            }
            int state = isIntersect(ps1, pe1, ps2, pe2);
            if (state == LINE) printf("LINE\n");
            else if (state == NONE) printf("NONE\n");
            else {
                getInterPoint(ps1, pe1, ps2, pe2);
                printf("POINT %.2f %.2f\n", ans[0], ans[1]);
            }
        }
        printf("END OF OUTPUT\n");
    }
    return 0;
}