线段问题

解题思路：

本题我们判断是否存在一条直线，使得给定的 $n$ 条线段在直线上的投影存在公共部分。

如果存在一条直线，能穿过 $n$ 条线段，那么此时我们在直线上任意一点做一条垂线，$n$ 条线段在垂线上的投影是一定有公共部分的。

反过来，如果存在一条直线，使得 $n$ 条线段在该直线上的投影存在公共部分，那么我们在这个公共部分中任意取一个点做一条垂线，则这条垂线也一定穿过 $n$ 条线段。

因此原问题就等价于判断存在一条直线穿过 $n$ 条线段。那么我们接下来是需要判断是否存在一条直线穿过 $n$ 条线段。

对于任意一条穿过 $n$ 条线段的直线，如果这条直线没有经过任意一条线段的端点，则我们可以将这条直线左右旋转，将它卡在某一个线段的端点上，我们在将这条线段以这个端点为中心旋转，将它卡在另一个线段的端点上。此时这条直线刚好卡在某两个线段的端点上。通过这个方法我们能将任意一条穿过 $n$ 条线段的直线通过旋转变成经过某两个线段的端点的直线。

通过这个思路，我们可以直接枚举任意两个线段的端点，如果某两个线段的端点构成的直线能穿过 $n$ 条线段，就有解，如果所有线段的端点构成的线段都不能穿过 $n$ 条线段，就无解。

然后对于任意一条直线，如何判断它能都穿过 $n$ 条线段呢，其实就是判断一下每条线段的两个端点是否都在直线的两侧，这只需要取直线上一点 $p$，取直线上任意向量 $\vec{w}$，对于线段 $(u,v)$，如果 $(\vec{w} \times \vec{pu})(\vec{w} \times \vec{pv}) \leq 0$，说明直线一定在该线段上，这其实就是一个简化版的跨立实验。

本题枚举直线需要 $O(n^2)$ 的复杂度，对于每条直线还需要判断是否穿过 $n$ 条线段，因此整个的时间复杂度是 $O(n^3)$

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 210;
const double eps = 1e-8;

int n;
//q 存储所有端点
//a[i] 表示第 i 个线段的左端点
//b[i] 表示第 i 个线段的右端点
PDD q[N], a[N], b[N];

int sign(double x) //符号函数：x == 0 返回 0，x < 0 返回 -1，x > 0 返回 1
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int cmp(double x, double y) //比较函数：x == y 返回 0，x < y 返回 -1，x > y 返回 1
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

double cross(double x1, double y1, double x2, double y2) //求 x1y1 和 x2y2 的叉积
{
    return x1 * y2 - x2 * y1;
}

double area(PDD a, PDD b, PDD c) //求 ab 和 ac 构成的平行四边形的有向面积
{
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

bool check() //判断是否存在一条直线能穿过 n 条线段
{
    for(int i = 0; i < n * 2; i++)
        for(int j = i + 1; j < n * 2; j++)
        {
            if(!cmp(q[i].x, q[j].x) && !cmp(q[i].y, q[j].y)) continue; //如果两个点重合，直接跳过
            bool flag = true; //记录当前直线是否穿过所有线段
            for(int k = 0; k < n; k++)
                if(sign(area(q[j], q[i], a[k])) * sign(area(q[j], q[i], b[k])) > 0) //说明直线不穿过当前线段
                {
                    flag = false; //修改标记
                    break;
                }
            if(flag) return true; //如果当前直线穿过所有线段，返回 true
        }
    return false; //到这说明不存在直线穿过 n 条线段，返回 false
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0, k = 0; i < n; i++)
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            q[k++] = {x1, y1}, q[k++] = {x2, y2};
            a[i] = {x1, y1}, b[i] = {x2, y2};
        }

        if(check()) puts("Yes!");
        else puts("No!");
    }
    return 0;
}