POJ 1127 Jack Straws(线段相交判断+并查集)

POJ 1127 Jack Straws(线段相交判断+并查集)

http://poj.org/problem?id=1127

题意:

给你n条线段,然后你需要回答接下来的数个询问:第i条线段和第j条线段是否相交? (i与j通过别的线段间接相交也算他们两相交,且i线段与j线段交于端点也算相交)

分析:

首先把每条线段作为一个并查集,然后枚举两两线段,如果i和j相交,那么就合并他们的并查集. 最终对于每条询问,如果询问的两条线段属于同一个并查集,那么就输出” CONNECTED”,否则输出” NOT CONNECTED”.

判断两条线段是否相交,可以参考刘汝佳<<训练指南>>P258.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool InSegment(Point P,Point A,Point B)
{
    return dcmp(Cross(A-P,B-P))==0 && dcmp(Dot(A-P,B-P))<=0;
}
bool SegmentIntersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
    double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
    if(dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0) return true;
    if(dcmp(c1)==0 && InSegment(b1,a1,a2)) return true;
    if(dcmp(c2)==0 && InSegment(b2,a1,a2)) return true;
    if(dcmp(c3)==0 && InSegment(a1,b1,b2)) return true;
    if(dcmp(c4)==0 && InSegment(a2,b1,b2)) return true;
    return false;
}
/***刘汝佳模板***/
const int maxn=10+5;
Point seg[maxn][2];
int fa[maxn];
int findset(int x)
{
    return fa[x]==-1?x: fa[x]=findset(fa[x]);
}
void bind(int i,int j)
{
    int fi=findset(i);
    int fj=findset(j);
    if(fi!=fj) fa[fi]=fj;
}


int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=1;i<=n;++i)
            scanf("%lf%lf%lf%lf",&seg[i][0].x,&seg[i][0].y,&seg[i][1].x,&seg[i][1].y);
        memset(fa,-1,sizeof(fa));

        for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        if(SegmentIntersection(seg[i][0],seg[i][1],seg[j][0],seg[j][1]))
            bind(i,j);
        int i,j;
        while(scanf("%d%d",&i,&j)==2)
        {
            if(i==0 && j==0) break;
            if(findset(i)==findset(j)) printf("CONNECTED\n");
            else printf("NOT CONNECTED\n");
        }
    }
    return 0;
}