POJ 3304：Segments & Acwing 2984：线段（计算几何基础枚举判断点在直线两侧）

旧城等待， 2022-10-23 09:52 224阅读 0赞

### 题目链接 ###

[POJ 3304：Segments][POJ 3304_Segments]  
[Acwing 2984：线段][Acwing 2984]

### 题目大意 ###

有n条线段，给出所有线段的两端点，判断是否存在一条直线，使得所有线段到这条直线上的投影都有交点，若存在输出Yes!，否则输出No!。

### 思路 ###

首先要找这条直线不好直接找，所以我们就要将问题转化一下，若存在一条直线1和所有线段都有交点，则一定存在一条和该直线垂直的直线2，使得所有线段到直线2上的投影都有交点，交点就是所有线段和直线1的交点在直线2上的投影。如下图：  
![eg][]  
那么这样就好找这条直线了，因此这就将问题**转化成了求一条直线和所有线段都有交点**，那么现在如何求这条直线呢？我们考虑将这条直线绕任意一点旋转，那么他一定会被一条线段所限制，他最多可旋转到某条直线的一个端点，如图：  
![eg][eg 1]  
这里的红色端点就是限制他的点，然后我们再绕该红色点旋转，一点还会有另一个蓝点来限制这条直线，如图：  
![eg][eg 2]  
因此，我们就会发现，这条直线在这种情况下一点会经过所有线段端点的某两个，因此我们只需要枚举两个点，然后再判断一次即可。那么问题来了如何判断直线是否和线段相交呢？我们可以用向量的叉积来判断，如图直线ij和线段ab相交：  
![eg][eg 3]  
做向量 j i ⃗ \\vec \{ji\} ji和 j a ⃗ \\vec \{ja\} ja和 j b ⃗ \\vec \{jb\} jb，若**a和b在直线的两侧**，则 j i ⃗ \\vec \{ji\} ji与 j a ⃗ \\vec \{ja\} ja的叉积一定和 j i ⃗ \\vec \{ji\} ji与 j b ⃗ \\vec \{jb\} jb的叉积符号相反，这里[在这有证明][Link 1]。  
枚举的复杂度是O(n2)，枚举每个线段判断是否相交的复杂度是O(n)。所以总复杂度就是O(n3)，n是1e2，t是1e2，最坏情况到1e8，但一般不会到最坏情况，勉强过得去。

### 代码详解 ###

#include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int N = 210;
    const double eps = 1e-8;
    typedef pair<double,double> PDD;	//pair来存点或向量，存横纵坐标
    
    int t,n;
    PDD p[N],a[N],b[N];
    
    int sign(double x)	//sign函数是取一个数的符号位
    { 
    	if(fabs(x) < eps)	//若double x是0，返回0
    		return 0;
    	if(x < 0)		//若是负数，返回-1
    		return -1;
    	return 1;		//正数返回1
    }
    
    double cross(PDD a,PDD b,PDD c)	//cross是求叉积
    { 
    	PDD u,v;	//定义两个向量
    	u = { b.first-a.first,b.second-a.second};	//向量u是ab向量
    	v = { c.first-a.first,c.second-a.second};	//向量v是ac向量
    	return u.first*v.second - v.first*u.second;	//求uv叉积，就是x1*y2 - x2*y1
    }
    
    bool judge()
    { 
    	for(int i = 0;i < n*2;i++)	//枚举所有点，共2n个点
    	{ 
    		for(int j = i+1;j < n*2;j++)
    		{ 
    			if(fabs(p[i].first-p[j].first) < eps && fabs(p[i].second-p[j].second) < eps)	//若两点是重合的，没法构成直线，直接continue
    				continue;
    			bool fg = 0;
    			for(int k = 0;k < n;k++)	//判断所有线段
    			{ 
    				if(sign(cross(p[i],p[j],a[k])) * sign(cross(p[i],p[j],b[k])) > 0)	//如果两个叉积相乘大于0，说明两叉积同号，两点在直线同一侧
    				{ 
    					fg = 1;		//标记
    					break;		//退出
    				}
    			}
    			if(fg == 0)	//如果循环完都没被标记，说明都有交点
    				return 1;
    		}
    	}
    	return 0;
    }
    
    int main()
    { 
    	cin >> t;
    	while(t--)
    	{ 
    		cin >> n;
    		int cnt = 0;
    		for(int i = 0;i < n;i++)
    		{ 
    			double x1,x2,y1,y2;
    			cin >> x1 >> y1 >> x2 >> y2;
    			p[cnt++] = { x1,y1},p[cnt++] = { x2,y2};	//p存下所有点
    			a[i] = { x1,y1},b[i] = { x2,y2};		//a存第i条线段的左端点，b是右端点
    		}
    
    		if(judge())
    			cout << "Yes!" << endl;
    		else
    			cout << "No!" << endl;
    	}
    
    	return 0;
    }

[POJ 3304_Segments]: http://poj.org/problem?id=3304
[Acwing 2984]: https://www.acwing.com/problem/content/description/2987/
[eg]: /images/20221023/4445afce1fd34df484d50b758b29d8b0.png
[eg 1]: /images/20221023/b57336b42a4040bcb8949d86c9d195f2.png
[eg 2]: /images/20221023/07b67ab8f849476dbc88be9683fbf3f5.png
[eg 3]: /images/20221023/5fbce7efe1fe4477999c59b7ae0d8b86.png
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/114382634