【POJ-3304】Segments【直线与线段相交】

【POJ-3304】Segments【直线与线段相交】

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

Solution:

题目问是否存在至少一条直线使得所有线段在该直线上的投影能够相交在至少一点上,如果我们取该直线这样的一个点,做该直线的垂线,必然有该直线穿过所有线段,同样的我们也能够发现,如果我们可以找到一条过所有线段的直线,那么我们对该直线做的任意垂线都满足题意,那么我们只要找到这样一条直线就好。

点的坐标是实数,实数是不可数集,我们显然无法枚举空间内的所有直线。我们需要一个更加“极端”的方法,如果存在这样的直线,我们设想所有这样的直线构成一个集合,那么这个集合中极端位置的直线应当满足什么条件,显然,极端直线会通过至少2个已知线段的端点,那么我们可以枚举所有端点构成的直线来判断就可以了。需要注意,可能存在多个相同的端点,所以如果两个端点是相同的,那么是无法拉出一条直线的,需要在枚举时跳过这种情况。

由于判断的是直线与线段相交,我们的判定方法可以比判断线段与线段相交的时候简化,只需要判断直线上两点与线段两点构成的两个三角形的旋转方向【顺时针/逆时针/共线】就好。

#include <iostream>
#include <cmath>
// #define DBG
using namespace std;

typedef long double LD;
const int LIM = 100 + 10;
const LD EPS = 1e-8;
struct Point {
    LD x, y;
    LD cross(const Point &p) const {
        return x * p.y - y * p.x;
    }
};
Point ps[LIM * 2];
int t, n;
inline LD dist(const Point &a, const Point &b) {
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
bool isAns(const Point &a, const Point &b) {
    Point tmp = {b.x - a.x, b.y - a.y};
    for (int i = 0; i < n * 2; i += 2) {
        Point ta = {ps[i].x - a.x, ps[i].y - a.y};
        Point tb = {ps[i + 1].x - a.x, ps[i + 1].y - a.y};
        if (tmp.cross(ta) * tmp.cross(tb) > EPS)
            return false;
    }
    return true;
}

int main(void) {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int size = n * 2;
        for (int i = 0; i < size; i += 2)
            scanf("%Lf%Lf%Lf%Lf", &ps[i].x, &ps[i].y, &ps[i + 1].x, &ps[i + 1].y);
        bool flag = true;
        for (int i = 0; flag && i < size; i++) {
            for (int j = i + 1; flag && j < size; j++) {
                if (dist(ps[i], ps[j]) < EPS) continue;
                if (isAns(ps[i], ps[j]) || isAns(ps[j], ps[i]))
                    flag = false;
            }
        }
        if (flag) printf("No!\n");
        else printf("Yes!\n");
    }
    return 0;
}