Poj 3304 Segments (直线与线段交)

一时失言乱红尘 2023-01-19 11:58 221阅读 0赞

参考了 http://blog.csdn.net/heartnheart/article/details/5924116

题意：给出n条线段，判断是否存在有一条直线，满足所有的线段在直线上投影后至少有一个公共点

方法：原命题等价为存在一条直线穿过所有的线段（易知过公共点且垂直于所求直线的直线符合条件，设为直线a），该命题又等价于从所有线段中任选两端点形成的直线存在可以穿过所有的线段的直线（可将a平移至一条线段端点，然后绕这点旋转，使a过另一条线段端点）

注意 n==1的情况

#include <cmath>
    #include <cstdio>
    #include <cstring>
    
    const int N=205;
    const double STD=1e-9;
    
    int n;
    
    template<typename Type>
    class Point
    {
    public:
    	Type x,y;
    	Point(){}
    	Point (Type _x,Type _y)
    	{x=_x;y=_y;}
    	Point operator-(const Point &b) const
    	{return Point(x-b.x,y-b.y);}
        //调用点a的该函数
        //返回正值点a在向量bc的左侧
        //返回负值点a在向量bc的右侧
        //返回0点a在向量bc这条直线上
    	Type Cross (Point b,Point c)
    	{return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);}
    };
    Point <double> data[N];
    
    int DB(double x)
    {
    	if (fabs(x)<STD) return 0;
    	return x>0?1:-1;
    }
    
    //判断直线ab是否与线段cd相交
    //0 不相交
    //1 规范相交
    //2 不规范相交
    int SegLineCross (Point<double> a,Point<double> b,Point<double> c,Point<double> d)
    {
        int d1=DB(a.Cross(b,c));
        int d2=DB(a.Cross(b,d));
        if ((d1^d2)==-2)//注意加小括号，^的优先级比==低
            return 1;
        if (d1==0||d2 == 0)
            return 2;
        return 0;
    }
    
    bool Judge (Point<double> a,Point<double> b)//判断直线ab是否与所有线段相交
    {
        if (DB(a.x-b.x)==0 && DB(a.y-b.y)==0)//判断重复点
            return false;
        for (int i=1;i<2*n;i+=2)
            if (SegLineCross(a,b,data[i],data[i+1])==0)
                return false;
        return true;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    	    scanf("%d",&n);
    	    for (i=1;i<=2*n;i++)
                scanf("%lf%lf",&data[i].x,&data[i].y);
            if (n==1)
            {
                printf("Yes!\n");
                continue;
            }
            bool flag=false;
            for (i=1;i<=2*n;i++)
                for (int j=i+1;j<=2*n;j++)
                    if (Judge(data[i],data[j]))
                    {
                        flag=true;
                        break;
                    }
            if (flag) printf("Yes!\n");
            else printf("No!\n");
    	}
    	return 0;
    }