【POJ-1410】Intersection【注意题目的坑】

【POJ-1410】Intersection【注意题目的坑】

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

Solution:

问题十分简单,如果线段与矩形有:相交、相切、包含于,这三者关系之一的话,就输出T,反之输出F,那么思路就是,首先判断一下端点在不在矩形内部,如果在则必然是T,如果不在则可能是F也可能是端点不在矩形内的相交,对于端点不在矩形内的相交,只要和矩形的两条对角线判断一下相交就好了。

关键的难点是,需要注意到”The terms top left and bottom right do not imply any ordering of coordinates.”,意思就是,输入比较皮,输入的左上角坐标不一定是左上角,右下角坐标也不一定是右下角,需要手动调整一下正确的左上角和右下角。

#include <iostream>

using namespace std;

struct Point {
    int x, y;
    Point operator - (Point &p) {
        Point retv = {x - p.x, y - p.y};
        return retv;
    }
    // cross product
    int operator ^ (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;}
inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

enum {CLOCK = -1, COL, COUNTER};
int getOrientation(Point &a, Point &b, Point &c) {
    Point v1 = b - a, v2 = c - a;
    int ans = v1 ^ v2;
    if (ans < 0) return CLOCK;
    else if (ans == 0) return COL;
    return COUNTER;
}
bool onSegment(Point &s, Point &e, Point &p) {
    return p.x >= mini(s.x, e.x) && p.x <= maxi(s.x, e.x)
        && p.y >= mini(s.y, e.y) && p.y <= maxi(s.y, e.y);
}
bool isIntersect(Point &s1, Point &e1, Point &s2, Point &e2) {
    int o1 = getOrientation(s1, s2, e1);
    int o2 = getOrientation(s1, e2, e1);
    int o3 = getOrientation(s2, s1, e2);
    int o4 = getOrientation(s2, e1, e2);
    if (o1 != o2 && o3 != o4) return true;
    if (!o1 && !o2
        && mini(s1.x, e1.x) <= mini(s2.x, e2.x)
        && maxi(s1.x, e1.x) >= maxi(s2.x, e2.x)) return true;
    return false;
}

bool inArea(Point &p, Point &lt, Point &rb) {
    return p.x >= lt.x && p.x <= rb.x
        && p.y >= rb.y && p.y <= lt.y;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    Point s, e, lt, rb;
    while (n--) {
        cin >> s.x >> s.y >> e.x >> e.y >> lt.x >> lt.y >> rb.x >> rb.y;
        if (lt.x > rb.x) swap(lt.x, rb.x);
        if (lt.y < rb.y) swap(lt.y, rb.y);
        if (inArea(s, lt, rb) || inArea(e, lt, rb)) {
            cout << "T\n";
            continue;
        }
        Point lb = {lt.x, rb.y}, rt = {rb.x, lt.y};
        if (isIntersect(s, e, lt, rb) || isIntersect(s, e, lb, rt)) {
            cout << "T\n";
            continue;
        }
        cout << "F\n";
    }
    return 0;
}