HDU 1558 Segment set， 计算几何+并查集
题目：
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。
具体情况如下图所示：（这里利用了向量叉积来判断两个向量是否位于另一向量的两侧）
注意：只有同时满足以上两个条件，即相互跨立对方，两个线段才相交。
代码：
[cpp]
struct Point{
double x,y;
};
double direction(Point p0,Point p1,Point p2)
{
return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y);
}
bool on_segment(Point p0,Point p1,Point p2)
{
if((min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && (min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y)))
return true;
return false;
}
bool Segment_intersect(Point p1,Point p2,Point p3,Point p4)
{
double d1,d2,d3,d4;
d1 = direction(p3,p4,p1);
d2 = direction(p3,p4,p2);
d3 = direction(p1,p2,p3);
d4 = direction(p1,p2,p4);
if(((d1>0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)||(d3<0&&d4>0)))
return true;
else if(d1==0 && on_segment(p3,p4,p1))
return true;
else if(d2==0 && on_segment(p3,p4,p2))
return true;
else if(d3==0 && on_segment(p1,p2,p3))
return true;
else if(d4==0 && on_segment(p1,p2,p4))
return true;
return false;
}
知道了怎样判断两线是否相交后， 一切都好办。
接下来要做的是， 每次添加一条直线是，都进行并查集的Union操作。
如果要知道第k条线所在的集合有几条线段，只需要判断并查集中所有以k的跟结点为跟结点的数量有几个即可
AC代码：
[cpp]
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define N 1005
using namespace std;
struct Point2D //二维平面点
{
double x,y;
Point2D():x(0),y(0){}
Point2D(double x,double y):x(x),y(y){}
double Mod() const {return sqrt(x*x + y*y);}
friend Point2D operator-(const Point2D& lh,const Point2D& rh){
return Point2D(lh.x-rh.x, lh.y-rh.y);
}
friend double operator&(const Point2D& lh,const Point2D& rh){
return lh.x*rh.y - lh.y*rh.x;
}
friend std::istream& operator>>(std::istream& in, Point2D& pt){
in>>pt.x>>pt.y;
return in;
}
};
struct Segment2D{
Point2D bgn, end;
Segment2D():bgn(),end(){}
Segment2D(Point2D b,Point2D e):bgn(b),end(e){}
Segment2D(double x1,double y1,double x2,double y2):bgn(x1,y1),end(x2,y2){}
friend std::istream& operator>>(std::istream& in, Segment2D& pt){
in>>pt.bgn>>pt.end;
return in;
}
friend std::ostream& operator<< (std::ostream& out, Segment2D& pt){
out<<pt.bgn.x<<" "<<pt.bgn.y<<" "<<pt.end.x<<" "<<pt.end.y;
return out;
}
};
bool SegmentIntersect(const Segment2D& u, const Segment2D& v)
{
//1.快速排斥试验,不相交返回0
if((max(u.bgn.x,u.end.x)>=min(v.bgn.x,v.end.x))&&
(max(v.bgn.x,v.end.x)>=min(u.bgn.x,u.end.x))&&
(max(u.bgn.y,u.end.y)>=min(v.bgn.y,v.end.y))&&
(max(v.bgn.y,v.end.y)>=min(u.bgn.y,u.end.y)));
else return false;
//2.跨立实验,u的两端点在v两侧，并且v的两端点在u两侧
if((((u.bgn-v.bgn)&(v.end-v.bgn))*((v.end-v.bgn)&(u.end-v.bgn))>=0)&&
(((v.bgn-u.bgn)&(u.end-u.bgn))*((u.end-u.bgn)&(v.end-u.bgn))>=0))
return true;
else return false;
}
Segment2D arr[N];
int Index, dnum[N];
int father[N];
void init(){
for(int i=0; i<N; ++i)
&nbs
补充：软件开发 , C++ ,
