Jack Straws(判断线段是否相交 + 并查集)

/**
 
题意:
   判断线段是否相交  (包括间接相交)
   输入:
    N(代表有n条线段)
    sx  sy  ex  ey(一条直线的两端点的坐标)
    ;
    ;
    ;
    a b(判断第a条和第b条线段是否相交)
    :
    :
     :
    0 0输入0 0 询问结束
    输出:若相交输出  CONNECTED
          否则         NOT CONNECTED
*/
 
Jack Straws(判断线段是否相交  + 并查集)
 
#include<stdio.h>
#include<iostream>
using namespace std;
struct node
{
    int sx,sy;
    int ex,ey;
} bian[20];
int vest[20];
bool isXiangJiao(node a,node b)///根据两条向量的积 来判断两条直线段的夹角  (看图解)
{
    int d1,d2,d3,d4;
    d1=(a.ex-a.sx)*(b.sy-a.sy)-(a.ey-a.sy)*(b.sx-a.sx);
    d2=(a.ex-a.sx)*(b.ey-a.sy)-(a.ey-a.sy)*(b.ex-a.sx);
    d3=(b.ex-b.sx)*(a.sy-b.sy)-(b.ey-b.sy)*(a.sx-b.sx);
    d4=(b.ex-b.sx)*(a.ey-b.sy)-(b.ey-b.sy)*(a.ex-b.sx);
    if(d1*d2<=0&&d3*d4<=0)return true;
    else return false;
}
void init(int n)
{
    for(int i=0; i<=n; i++)
        vest[i]=i;
}
int Find(int t)
{
    if(vest[t]==t)return t;
    return Find(vest[t]);
}
bool merge(int a,int b)
{
    int x=Find(a);
    int y=Find(b);
    if(x!=y)
    {
        vest[x]=y;
        return true;
    }
    return false;
}
void panDuan(int n)
{
    for(int i=1;i<=n-1;i++)
    {
        if(isXiangJiao(bian[i],bian[n]))
        {
             merge(i,n);///若相交 讲两条线段加入同一个集合内
        }
 
    }
}
bool isGuanXi(int a,int b)
{
    if(Find(a)==Find(b))return true;
    return false;
}
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        init(n);
        for(int i=1; i<=n; i++)
        {
             scanf("%d%d%d%d",&bian[i].sx,&bian[i].sy,&bian[i].ex,&bian[i].ey);
             panDuan(i);///向前比较是否和此条线段相交
        }
        int a,b;
        while(scanf("%d%d",&a,&b))
        {
            if(a==0&&b==0)break;
            if(isGuanXi(a,b))///判断 两条线段是否有关系
            {
                printf("CONNECTED\n");
            }
            else printf("NOT CONNECTED\n");
        }
    }
    return 0;
}
上一篇:js正则验证手机号


下一篇:【UGUI】ScrollRect 动态缩放格子大小,自动定位到中间的格子