学步园

屌丝真心觉得这题的计算几何味道远大于并查集，花了两天时间才想明白怎么判断两条直线相交，结果还写不对，。。。。。

code：

#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8;

int decmp(double n)
{
    if(fabs(n)<eps)
    {
        return 0;
    }
    return n>0 ? 1:-1;
}

struct Point
{
    double x,y;
};
struct Seg
{
    Point s,e;
}segs[1001];

double direction(Point l,Point r,Point m)
{
    //vector a (l.x-m.x,l.y-m.y)
    //vector b (r.x-m.x,r.y-m.y)
    return (l.x-m.x)*(r.y-m.y) - (r.x-m.x)*(l.y-m.y);
}
bool isIntersert(Seg a,Seg b)
{
    int d1,d2,d3,d4;
    d1=decmp(direction(a.s,a.e,b.s));
    d2=decmp(direction(a.s,a.e,b.e));
    d3=decmp(direction(b.s,b.e,a.s));
    d4=decmp(direction(b.s,b.e,a.e));
    //规范相交
    if( d1*d2 <0 && d3*d4 <0)
    {
        return true;
    }
    //端点相交
    if( d1*d2 ==0 || d3*d4==0 )
    {
        return true;
    }
    return false;
}

int num[1001],rank[1001],fa[1001];
void init()
{
    for(int i=1;i<=1000;i++)
    {
        num[i]=1;
        rank[i]=0;
        fa[i]=i;
    }
}
int find(int k)
{
    if(k!=fa[k])
    {
        fa[k]=find(fa[k]);
    }
    return fa[k];
}
void merge(int x,int y)
{
    if(!isIntersert(segs[x],segs[y]))
    {
        return ;
    }
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        if(rank[x]<rank[y])
        {
            fa[x]=y;
            num[y]+=num[x];
        }else{
            fa[y]=x;
            num[x]+=num[y];
            if(rank[x]==rank[y])
            {
                rank[x]++;
            }
        }
    }
}
int main()
{
    int cas,n,cnt,i,j,k;
    char str[2];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        cnt=0;
        init();
        for(i=1;i<=n;i++)
        {
            scanf("%s",str);
            if(str[0]=='P')
            {
                ++cnt;
                scanf("%lf%lf",&segs[cnt].s.x,&segs[cnt].s.y);
                scanf("%lf%lf",&segs[cnt].e.x,&segs[cnt].e.y);
                for(j=1;j<cnt;j++)
                {
                    merge(j,cnt);
                }
            }else{
                scanf("%d",&k);
                k=find(k);
                printf("%d\n",num[k]);
            }
        }
        if(cas)
        {
            puts("");
        }
    }
    return 0;
}