#P3304. Segments

    ID: 2305 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>难度入门搜索枚举Amirkabir University of Technology Local Contest 2006

Segments

题目描述

给定二维空间中的nn条线段,判断是否存在一条直线,使得所有线段在该直线上的投影至少有一个公共点。

输入格式

第一行:测试用例数量TT
每个测试用例:
第一行:线段数量nnn100n \leq 100)。
接下来nn行:每行四个实数x1 y1 x2 y2x_1\ y_1\ x_2\ y_2,表示一条线段的两个端点坐标。
浮点数比较时,若ab<108|a - b| < 10^{-8}则认为相等。

输出格式

对每个测试用例,若存在满足条件的直线,输出"Yes!""Yes!",否则输出"No!""No!"

样例输入 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!

样例解释

11. 第一组数据:两条线段共线,存在无数条满足条件的直线(如垂直于它们的直线)。
22. 第二组数据:三条线段的投影在垂直方向上有重叠。
33. 第三组数据:无法找到一条直线使所有投影相交。

关键思路

11. 问题转化:线段投影有公共点 ⇔ 存在一条直线能与所有线段相交(即该直线是它们的共同相交直线)。
22. 枚举候选直线
若所有线段互相相交,则答案为"Yes!""Yes!"
否则,候选直线需通过某两条线段的端点,检查是否能与所有线段相交。
33. 计算几何:利用叉积判断直线与线段是否相交。

来源

Amirkabir University of Technology Local Contest 20062006