Intersection

题目链接

[POJ 1410] Intersection

题解

简单题。给定一个线段与一个矩形,判断它们有无公共点。
计算几何基础,首先判断线段是否在矩形内部,其次判断它们有无交点。

代码

#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1ll << 60;
long double T, x1, x2, yy1, y2, l, r, t, d;

int main() {
    cin >> T;
    while (T--) {
        cin >> x1 >> yy1 >> x2 >> y2 >> l >> t >> r >> d;
        if (l > r)swap(l, r);
        if (d > t)swap(d, t);
        if (x1 <= r && x2 <= r && yy1 <= t && y2 <= t && x1 >= l && x2 >= l && yy1 >= d && y2 >= d) {
            cout << "T" << endl;
            continue;
        }
        if (x1 == x2) {
            if (x1 >= l && x1 <= r && max(yy1, y2) >= d && min(yy1, y2) <= t) {
                cout << 'T' << endl;
            }
            else cout << 'F' << endl;
            continue;
        }
        if (yy1 == y2) {
            if (yy1 >= d && yy1 <= t && max(x1, x2) >= l && min(x1, x2) <= r) {
                cout << 'T' << endl;
            }
            else cout << 'F' << endl;
            continue;
        }
        long double temp;
        temp = (t - y2) / (yy1 - y2)*(x1 - x2) + x2;
        if (temp >= min(x1, x2) && temp <= max(x1, x2) && temp >= l && temp <= r) {
            cout << "T" << endl;
            continue;
        }
        temp = (d - y2) / (yy1 - y2)*(x1 - x2) + x2;
        if (temp >= min(x1, x2) && temp <= max(x1, x2) && temp >= l && temp <= r) {
            cout << "T" << endl;
            continue;
        }
        temp = (l - x2) / (x1 - x2)*(yy1 - y2) + y2;
        if (temp >= min(yy1, y2) && temp <= max(yy1, y2) && temp >= d && temp <= t) {
            cout << "T" << endl;
            continue;
        }
        temp = (r - x2) / (x1 - x2)*(yy1 - y2) + y2;
        if (temp >= min(yy1, y2) && temp <= max(yy1, y2) && temp >= d && temp <= t) {
            cout << "T" << endl;
            continue;
        }
        cout << "F" << endl;
    }
}

标签: math, geometry

添加新评论