題目：
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)
father[i]=i, dnum[i] = 1;
}
int find(int x){
int i, j=x;
while(j!=father[j]) j=father[j];
while(x!=j){
i = father[x];
father[x] = j;
x = i;
}
return j;
}
void Union(int x, int y){
int a = find(x);
int b = find(y);
if(a!=b)
father[a] = b;
}
int main(){
freopen("input.txt", "r", stdin);
int T,n,k,cas=1;
char cmd[2];
scanf("%d",&T);
while(T--){
scanf("%d", &n);
memset(dnum, 0, sizeof(dnum));
Index=0;
init();
while(n--){
scanf("%s", cmd);
if(cmd[0]=='P'){
cin >> arr[++Index];
for(int i=1; i<=Index-1; ++i){
if(SegmentIntersect(arr[i], arr[Index]))
Union(i, Index);
}
}
else if(cmd[0] == 'Q'){
scanf("%d", &k);
int x=find(k);
int cnt=0;
for(int i=1; i<=Index; ++i){
if(x==find(i))
++cnt;
}
cout << cnt << endl;
}
}
if(T) printf("\n");
}
return 0;
}
作者：shuangde800
