#P3304. Segments
Segments
题目描述
给定二维空间中的条线段,判断是否存在一条直线,使得所有线段在该直线上的投影至少有一个公共点。
输入格式
第一行:测试用例数量。
每个测试用例:
第一行:线段数量()。
接下来行:每行四个实数,表示一条线段的两个端点坐标。
浮点数比较时,若则认为相等。
输出格式
对每个测试用例,若存在满足条件的直线,输出,否则输出。
样例输入 1
3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0
样例输出 1
Yes!
Yes!
No!
样例解释
. 第一组数据:两条线段共线,存在无数条满足条件的直线(如垂直于它们的直线)。
. 第二组数据:三条线段的投影在垂直方向上有重叠。
. 第三组数据:无法找到一条直线使所有投影相交。
关键思路
. 问题转化:线段投影有公共点 ⇔ 存在一条直线能与所有线段相交(即该直线是它们的共同相交直线)。
. 枚举候选直线:
若所有线段互相相交,则答案为。
否则,候选直线需通过某两条线段的端点,检查是否能与所有线段相交。
. 计算几何:利用叉积判断直线与线段是否相交。
来源
Amirkabir University of Technology Local Contest