hdu15558(线段相交判定）

最新推荐文章于 2021-03-12 11:59:48 发布

ACder_chen

最新推荐文章于 2021-03-12 11:59:48 发布

阅读量655

点赞数

分类专栏：并查集文章标签：判断线段相交

本文链接：https://blog.csdn.net/qqchenjunwei/article/details/23118049

版权

并查集专栏收录该内容

17 篇文章

订阅专栏

本文介绍了一种用于判断线段是否相交的算法，并利用并查集来处理一系列线段间的连通性问题。通过输入线段的坐标，程序能够有效地找出所有相交线段组成的组，并统计每组中的线段数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
#define SIZE 1001

struct point{

       double x,y;

}line[SIZE][2];

int num[SIZE];
int p[SIZE];


inline bool across(int i,int j)
{
       double x1,x2,x3,y1,y2,y3;
       x1=line[i][0].x-line[j][0].x;
       y1=line[i][0].y-line[j][0].y;
       x2=line[j][1].x-line[j][0].x;
       y2=line[j][1].y-line[j][0].y;
       x3=line[i][1].x-line[j][0].x;
       y3=line[i][1].y-line[j][0].y;
       return (x1*y2-x2*y1)*(x2*y3-x3*y2)>=0;
}

inline bool isRecIntersect(int i,int j)
{
       return max(line[i][0].x,line[i][1].x)>=min(line[j][0].x,line[j][1].x) &&
           max(line[i][0].y,line[i][1].y)>=min(line[j][0].y,line[j][1].y);
       }

inline bool isIntersect(int i,int j)
{
    return isRecIntersect(i,j)&&isRecIntersect(j,i)&&across(i,j)&&across(j,i);

}

int find(int x)
{
    return x == p[x] ? x:p[x] = find(p[x]);
}


void merge(int x,int y)
{
     int fx=find(x),fy=find(y);

     if(fx!=fy&&isIntersect(x,y))
     {
        p[fx] = fy;
        num[fy] += num[fx];
     }
}

void init(int n) {

    for(int i = 1; i  <= n; i++) {

        num[i] = 1;
        p[i] = i;
    }
}

int main()
{
    int cas;
    cin>>cas;
    while(cas--)
    {

        int c;
        int i;
        int n=1;
        cin>>c;
        init(c);
        while(c--)
        {
            char cmd[2];
            cin>>cmd;
            if(cmd[0]=='P')
            {
                cin>>line[n][0].x>>line[n][0].y>>line[n][1].x>>line[n][1].y;
                for(i=1;i<n;i++)
                    merge(i,n);
                n++;
            }
            else
            {
                cin>>i;
                cout<<num[find(i)]<<endl;
            }
        }
        if(cas)//if not the last cas
            puts("");
    }

    return 0;
}