题目描述

是否存在一条线，使得所有线段，在它上面的所有投影，都存在一个公共点

思路

应该转化一下，如果直接求这条直线$L$，那么可能暂时想不出什么好的思路与算法。

我们从投影点出发，所有线段在直线上的投影点，我们把这个点当做垂足，做一条直线$R$，那么这条垂线$R$，将会经过所有的线段。

同时，我们直观得(本人暂时无法证明)想想一下，这个直线$R$是否可以围绕某一点，进行旋转，并且保证，在一定的角度范围内旋转，仍然能满足能够穿过所有的线段。

那么它的范围的两个极值，就是我们点集内的两条直线。

那么接下来，这个问题就转化成，枚举点集内的两条直线，再判断这条直线是否穿过所有的线段。

如果存在这样的直线$R$，那么就是Yes!

代码如下

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const double eps=1e-8;
struct Point
{
    double x,y;
    Point (){}
    Point (double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x+B.x,y+B.y);}
    Point operator - (Point B){return Point(x-B.x,y-B.y);}
}p[1000],a[1000],b[1000];
int sgn(double x)
{
    if (fabs(x)<eps) return 0;
    return x<0?-1:1;
}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}

int  Point_line_relation(Point A,Point B,Point K)
{
    int c=sgn(Cross(K-A,B-A));
    if (c<0) return 1;
    if (c>0) return -1;
    return 0;
}
bool check(int n)
{
    for(int i=0;i<2*n;i++)
    {
        for(int j=i+1;j<2*n;j++)
        {
            if (!sgn(p[i].x-p[j].x)&&!sgn(p[i].y-p[j].y)) continue;//题目中说了，如果两个浮点数 a 与 b 满足 |a−b|<10−8，则你可以认为这两个数相等。
            bool flag=1;
            for(int k=0;k<n;k++)
            {
                if (Point_line_relation(p[i],p[j],a[k])*Point_line_relation(p[i],p[j],b[k])>0)//用向量R对线段两个点分别的叉乘的符号，来判断是否同侧
                {
                    flag=0;
                    break;
                }
            }
            if (flag) return 1;
        }
    }
    return 0;

}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,cnt=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)//a,b保存线段的两个端点  p代表的是点集
        {
            scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&b[i].x,&b[i].y);
            p[cnt++]=a[i];
            p[cnt++]=b[i];
        }
        if (check(n)) printf("Yes!\n");
        else printf("No!\n");
    }

    return 0;
}