HDU 1558 Segment set， 计算几何+并查集

题目链接：

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。

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

代码：

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代码：

#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;
}   

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double