POJ 3304(判断直线与线段位置关系)

本是古典何须时尚 2022-05-18 04:12 195阅读 0赞

题目大意：给出n条线段的坐标，问是否能找到一条直线使得所有线段投影到这条直线上至少相交于一点，如果能找到这条直线就输出Yes！，否则输出No！

分析：如果能找到一条直线（记为L1）与所有线段都有交点，那么做L1的垂线L2，垂足就是所有线段投影L2的交点。

枚举两两线段各一个端点，连接这条直线L3，再判断剩下的线段与这条直线是否有交点。证明：如果L3与所有线段都有交点，则保持和所有线段相交，左右平移到和某一线段相交到端点为止，然后绕这个交点旋转，旋转到和另一条线段交于另一个端点为止，这样就找到了L3'与所有线段相交，而且这条直线经过了两条线段的端点。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e2+7;
    const double eps = 1e-8;
    int T,n;
    
    struct Point{
        double x,y;
        Point(){}
        Point(double _x,double _y){x=_x;y=_y;}
    };
    
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){s=_s;e=_e;}
    }line[maxn];
    
    int sgn(double x)
    {
        if(fabs(x)<eps) return 0;
        else return x<0?-1:1;
    }
    
    double cross(Point a,Point b,Point c)
    {
        a.x-=c.x;a.y-=c.y;
        b.x-=c.x;b.y-=c.y;
        return a.x*b.y-a.y*b.x;
    }
    
    bool check(Line l1)
    {
        if(fabs(l1.s.x-l1.e.x)<eps&&fabs(l1.s.y-l1.e.y)<eps) return false;
        for(int i=0;i<n;i++)
            if(cross(line[i].s,l1.e,l1.s)*cross(line[i].e,l1.e,l1.s) > eps)
                return false;
        return true;
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            double x1,y1,x2,y2;
            for(int i=0;i<n;i++)
            {
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                line[i] = Line(Point(x1,y1),Point(x2,y2));
            }
            int flag = 0;
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(check(Line(line[i].s,line[j].s))||check(Line(line[i].s,line[j].e))||check(Line(line[i].e,line[j].s))||check(Line(line[i].e,line[j].e)))
                    {
                        flag = 1;
                        break;
                    }
            if(n<=2) flag = 1;
            if(flag) printf("Yes!\n");
            else printf("No!\n");
        }
        return 0;
    }