hdu1558（并查集）

这道题的难点在于如何判断两条线段是否有交点

首先，我们可以想象一下，两个线段如果相交，则从一条线段可以看到一个另一个线段的点在其两侧

如果设横向的为ab线段，cd为另一条边，可以发现abc与abd的旋转方向不相同。

由此我们得到以下算法

double imem(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);//判断旋转方向
}
           

其他还存在一种情况：

c在ab之间或者延长线上，此时上算法算出结果为0.所以我们需要加处理

bool if_in(node a,node b,node c)
{
    return c.x>=min(a.x,b.x) && c.x<=max(a.x,b.x)
        && c.y>=min(a.y,b.y) && c.y<=max(a.y,b.y);
}
           

这样判断出点是否在线上。

由此，获得了判断的结果

bool judge(node a,node b,node c,node d)
{
    double no1,no2,no3,no4;
    no1=imem(c,d,a);
    no2=imem(c,d,b);
    no3=imem(a,b,c);
    no4=imem(a,b,d);
    if(no1*no2<0 &&no3*no4<0) return true;
    if(no1==0 && ifin(c,d,a)) return true;
    else if(no2==0 && ifin(c,d,b)) return true;
    else if(no3==0 && ifin(a,b,c)) return true;
    else if(no4==0 && ifin(a,b,d)) return true;
    return false;
}
           

这个解决了，整个问题就很简单了，并查集的处理也很基础。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 1005
using namespace std;
int G[N],num[N];
struct node
{
    double x,y;
};
struct flow
{
    node node1,node2;
}Flow[N];
int findx(int x)
{
    return G[x]==x?x:G[x]=findx(G[x]);
}
void set(int a,int b)
{
    int p=findx(a),q=findx(b);
    if(p!=q)
    {
        G[p]=q;
        num[q]+=num[p];
    }
}
double imem(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool ifin(node a,node b,node c)
{
    return c.x>=min(a.x,b.x) && c.x<=max(a.x,b.x)
        && c.y>=min(a.y,b.y) && c.y<=max(a.y,b.y);
}
bool judge(node a,node b,node c,node d)
{
    double no1,no2,no3,no4;
    no1=imem(c,d,a);
    no2=imem(c,d,b);
    no3=imem(a,b,c);
    no4=imem(a,b,d);
    if(no1*no2<0 &&no3*no4<0) return true;
    if(no1==0 && ifin(c,d,a)) return true;
    else if(no2==0 && ifin(c,d,b)) return true;
    else if(no3==0 && ifin(a,b,c)) return true;
    else if(no4==0 && ifin(a,b,d)) return true;
    return false;
}
int main()
{
    int T,n,i,j,a,number;
    char ch[10];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        a=0;
        for(i=1;i<=n;i++)
        {
            G[i]=i;
            num[i]=1;
        }
        for(i=0;i<n;i++)
        {
           scanf("%s",&ch);
           if(ch[0]=='P')
           {
               a++;
               scanf("%lf%lf%lf%lf",&Flow[a].node1.x,&Flow[a].node1.y,&Flow[a].node2.x,&Flow[a].node2.y);
               for(int j=1;j<a;j++)
               {
                   if(findx(j)!=findx(a) &&judge(Flow[j].node1,Flow[j].node2,Flow[a].node1,Flow[a].node2))
                        set(j,a);
               }
           }
           else if(ch[0]=='Q')
           {
               scanf("%d",&number);
               number = findx(number);
               printf("%d\n",num[number]);
           }
        }
        if(T) printf("\n");
    }
    return 0;
}