POJ 3304 Segments 题解
2021-03-29 22:20 作者:昵称不能为空voidf | 我要投稿
题目大意：给定若干线段，问是否存在一条直线，使得这些线段在上面的投影有至少一个公共点。线段以实数格式的起点x，起点y，终点x，终点y格式给出。
刚上手的时候在想n^2内的搞法，一看范围才100条线，暴力完事了
思路：我们考虑题目中那条直线的法线，即垂直于题述直线的一条表示方向的线。每个线段在直线上的投影相当于每个线段的端点通过这条法线的方向连到直线上形成的两个点之间的一个区间。
考虑线段间端点的连线，将这条线作为上述的法线，则这两条线段最终在直线上的投影必定至少有1个交点。如果这条法线与任何线段都至少有一个公共点，那么可以说明以这条法线为法线的直线至少所有的线段在之上的投影都会有一个公共点。
那么我们之间枚举线段，用两条不同的线段的两个端点分别连线，再去暴力验证是否这条直线穿过所有线段即可。
实现细节比较多，过程中因为我没有用叉积算相交，所以对原有板子改造了不少地方。
首先我们需要一个四舍五入模块。我们希望精度可以调一处而动全身，所以把这个参数写在命名空间根位置。并且设置函数round_compare，把所有涉及实数比较的function都改为使用这个。
向量类与直线类的比较运算符需要重写。
直线类的判断平行，判断三点共线需要重写
为了判断直线的本质相等，我们引入直线归一化。即把直线一般式的A、B、C看成一个三维向量，如果他们之间线性相关，则为同一直线。那么我们运用向量的单位化于直线的比较。
最后我们需要一个线段类。这里的线段类派生自直线。
那么核心代码就可以写出来了
顺便屑站代码块是不是有点问题啊，<Segment2>写不上去啊（
