首页 / 软件开发 / 数据结构与算法 / HDU 1558：Segment set， 计算几何+并查集

HDU 1558：Segment set， 计算几何+并查集2014-10-11 csdn博客 shuangde800题目链接：

http://acm.hdu.edu.cn/showproblem.php？pid=1558

题目类型： 计算集合 ， 并查集

题目：

A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.

Sample Input

1 10 P 1.00 1.00 4.00 2.00 P 1.00 -2.00 8.00 4.00 Q 1 P 2.00 3.00 3.00 1.00 Q 1 Q 3 P 1.00 4.00 8.00 2.00 Q 2 P 3.00 3.00 6.00 -2.00 Q 5

Sample Output

1 2 2 2 5

题目大意：

输入几条线段，线段由坐标上的两点组成， 每一点有x，y，代表x轴和y轴对应的值。

当输入为Q  k时， 输出与第k条直线直接或间接有相连的线段条数。

分析与总结：

这一题是并查集比较基础的应用， 但是这题的关键在于判断两条直线是否相交。

断两线段是否相交的方法：    我们分两步确定两条线段是否相交：

1. 快速排斥试验：设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。

2. 跨立试验：如果两线段相交，则两线段必然相互跨立对方。 若P1P2跨立Q1Q2 ，则矢量 （ P1 - Q1 ） 和（ P2 - Q1 ）位于矢量（ Q2 - Q1 ） 的两侧，即： （（ P1 - Q1 ） × （ Q2 - Q1 ）） * （（ P2 - Q1 ） × （ Q2 - Q1 ）） < 0。（利用了向量叉积） 当 （ P1 - Q1 ） × （ Q2 - Q1 ） = 0 时，说明 （ P1 - Q1 ） 和 （ Q2 - Q1 ）共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，（ Q2 - Q1 ） ×（P2 - Q1 ） = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是：（（ P1 - Q1 ） × （ Q2 - Q1 ）） * （（ Q2 - Q1 ） × （ P2 - Q1 ）） >= 0。同理判断Q1Q2跨立P1P2的依据是：（（ Q1 - P1 ） × （ P2 - P1 ）） * （（ P2 - P1 ） × （ Q2 - P1 ）） >= 0。

具体情况如下图所示：（这里利用了向量叉积来判断两个向量是否位于另一向量的两侧） 注意：只有同时满足以上两个条件，即相互跨立对方，两个线段才相交。