寂寞外套

文章
5
资源
0
加入时间
2年10月17天

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

题目大意:给出n条线段的坐标,问是否能找到一条直线使得所有线段投影到这条直线上至少相交于一点,如果能找到这条直线就输出Yes!,否则输出No!分析:如果能找到一条直线(记为L1)与所有线段都有交点,那么做L1的垂线L2,垂足就是所有线段投影L2的交点。枚举两两线段各一个端点,连接这条直线L3,再判断剩下的线段与这条直线是否有交点。证明:如果L3与所有线段都有交点,则保持和所有线段相交,左右...